牛客编程巅峰赛S2第4场 - 钻石&王者 A-B

牛牛摆玩偶

https://ac.nowcoder.com/acm/contest/9476/A

牛客编程巅峰赛S2第4场 - 钻石&王者

A 牛牛摆玩偶

需要放置 $n(2 \leq n \leq 10^5)$ 个物品，每个物品都必须放在合法区间内，每个位置只能放一个物品。有 $m$ 个互不相交的区间 $(1\le m\le 10^5)$ ，题目希望相邻物品之间的距离的最小值越大越好，请输出这个值。

思路

二分答案 $mid$ ， $O(n)$ 或者 $O(nlog(n))$ 来 $check$ 。

我的做法貌似麻烦了一点，问题不大，欢迎提出你的做法。

因为区间两两不相交，但是我又不确定区间是否有序，所以我把区间左右端点全部用一个set保存起来，并记录一下是左端点还是右端点。

然后记录一下上一个玩偶放置的位置 $L$ ，用 $lowerbound$ 找到下一个可以放的位置：

如果是左端点，这一个就放在这里
如果是右端点，这一个就放在 $L+mid$

$check$ 看是否放置了 $n$ 个玩偶。

#define fi first
#define se second
#define mk make_pair
#define o2(x) (x) * (x)
#define eb emplace_back
#define SZ(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define clr(a, b) memset((a), (b), sizeof((a)))
#define GKD std::ios::sync_with_stdio(false);cin.tie(0)
#define rep(i, s, t) for(int i = (s), LIM=(t); i < LIM; ++i)
#define per(i, s, t) for(int i = (s), LIM=(t); i >= LIM; --i)
#define my_unique(x) sort(all(x)), x.erase(unique(all(x)), x.end())
typedef long long LL;
typedef long long int64;
typedef unsigned long long uint64;
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;// 998244353
const int MXN = 2e5 + 5;
const int maxn = 2e5 + 7;

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * @param n int整型 玩偶数
     * @param m int整型 区间数
     * @param intervals Interval类vector 表示区间
     * @return int整型
     */
    int doll(int n, int m, vector<Interval>& intervals) {
        // write code here
        LL L = 1, R = 1e10, mid, ans = 0;
        set<pii> mp;
        for(Interval x: intervals) {
            mp.insert(mk(x.start, 1));
            mp.insert(mk(x.end, 2));
        }
        auto check = [&](int mid) {
            LL L = -1e11;
            int cnt = 0;
            while(cnt < n) {
                auto p = mp.lower_bound(mk(L + mid, 0));
                if(p == mp.end()) return false;
                if((*p).se == 1) {
                    ++ cnt;
                    L = (*p).fi;
                }else if((*p).se == 2) ++ cnt, L = L + mid;
            }
            return cnt == n;
        };
        while(L <= R) {
            mid = (L + R) >> 1;
            if(check(mid)) ans = mid, L = mid + 1;
            else R = mid - 1;
        }
        return (int)ans;
    }
};

B 交叉乘

给你 $n$ 个数 $a_1,...,a_n$ ，多次询问，每次询问给你 $l,r(l\leq r)$ ，输出 $\sum_{i=l}^{r} \sum_{j=i+1}^{r} a_i*a_j$ 的值模1000000007。

思路

算贡献经典老题。

将答案补全为： $\sum_{i=l}^{r}a_i* \sum_{j=i+1}^{n}a_j - \sum_{i=l}^{r}a_i* \sum_{j=r+1}^{n} a_j$ 。

$O(n)$ 预处理出 $pre2[i]=\sum_{x=1}^i a-x, suf[i]=\sum_{x=i}^{n} a_x, ,pre[i]=a_i* \sum_{j=i+1}^{n}a_j$ 。

再 $O(n)$ 预处理 $pre[i]=\sum_{x=1}^{i}a_x* \sum_{j=x+1}^{n}a_j$ 。

然后就可以 $O(1)$ 回答答案了。

#define fi first
#define se second
#define mk make_pair
#define o2(x) (x) * (x)
#define eb emplace_back
#define SZ(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define clr(a, b) memset((a), (b), sizeof((a)))
#define GKD std::ios::sync_with_stdio(false);cin.tie(0)
#define rep(i, s, t) for(int i = (s), LIM=(t); i < LIM; ++i)
#define per(i, s, t) for(int i = (s), LIM=(t); i >= LIM; --i)
#define my_unique(x) sort(all(x)), x.erase(unique(all(x)), x.end())
typedef long long LL;
typedef long long int64;
typedef unsigned long long uint64;
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;// 998244353
const int MXN = 2e5 + 5;
const int maxn = 2e5 + 7;

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 多次求交叉乘
     * @param a int整型vector a1,a2,...,an
     * @param query int整型vector l1,r1,l2,r2,...,lq,rq
     * @return int整型vector
     */
    vector<int> getSum(vector<int>& a, vector<int>& query) {
        // write code here
        int n = a.si***t)query.size() / 2;
        vector<LL> suf(n + 1, 0), pre(n, 0), pre2(n, 0);
        per(i, n - 1, 0) {
            suf[i] = suf[i + 1] + a[i], suf[i] %= mod;
            if(i != n - 1) pre[i] = a[i] * suf[i + 1] % mod;
        }
        rep(i, 1, n) pre[i] = (pre[i] + pre[i - 1]) % mod;
        pre2[0] = a[0];
        rep(i, 1, n) pre2[i] = (pre2[i - 1] + a[i]) % mod;
        vector<int> ans, q(query);
        while(m --) {
            int R = q.back() - 1; q.pop_back();
            int L = q.back() - 1; q.pop_back();
            LL res = pre[R] - (L == 0? 0: pre[L - 1]);
            res %= mod;
            LL res2 = pre2[R] - (L == 0? 0: pre2[L - 1]);
            res2 %= mod;
            LL hou = 0;
            if(R != n - 1) hou = suf[R + 1];
            res = (res - res2 * hou % mod) % mod;
            res = (res + mod) % mod;
            ans.push_back((int)res);
        }
        reverse(all(ans));
        return ans;
    }
};