题解：AT_abc467_g [ABC467G] Many Sweets Problem

· · 题解

树套树做法太慢了，这里给出一种整体二分的做法。

因为带修，所以最好不要排序。我们尝试对每个询问在线地进行二分：我们二分最大的阈值 mid，使得 [l_i,r_i] 中所有不小于 mid 的数之和不小于 k。一次二分是 \mathcal{O}(m \log V) 的。

我们都知道二分是一种分治，我们可以将它看成在线段树上遍历一条由根到叶子的路径。如果直接在线进行二分的话，有很多点会被重复遍历。一个点被计算的这好几次，其实可以被合并到一次进行计算的。

具体地，我们将每一个值的出现和消失看作单点 +x 和单点 -x，原因见此处。于是我们便可以把这些操作和询问放到一起然后跑整体二分。

我们递归地解决这个问题：solve(l,r,E) 负责答案在 [l,r] 内的询问，以及绝对值值域在 [l,r] 中的操作。这些询问和操作都存储在 E 里面。

我们依次遍历这些事件，并使用一个轻量的 BIT 维护目前序列中所有处于 (mid,r] 中的数的和：

接着递归 solve(l,mid,E_l)，solve(mid+1,r,E_r)。

对于最终答案的统计，我们另开一个 BIT 维护目前有多少个 (mid,r] 的数，在遍历的顺便统计就好了。

结束条件就是 l = r，无解的处理就是 l = r = 0。

我们发现，树套树的两个维度分别对应了权值和区间。整体二分，不像树套树对第二维（区间）进行维护，而是直接实时计算，把所有调用通过一次计算搞定。所以空间小了，但是失去了在线功能。因为每个操作在每一层被处理了一次，时间为 \log n，因此总复杂度是 \mathcal{O}(m \log V \log n)。除此之外，整体二分拥有常数小，实现方便的优势。

// Problem: G - Many Sweets Problem
// Contest: AtCoder - AtCoder Beginner Contest 467
// Memory Limit: 1024 MB
// Time Limit: 3000 ms

#include <bits/stdc++.h>
#define int long long
#define Misaka namespace
#define Network std
using Misaka Network;

/*
if(s[i].id == 31) 
if(l == 0 && r == 250000000) 
*/

const int N = 1e5 + 7;
int n, q, a[N], m;
struct Event{
    int opt, id, ans;
    int c, x;
    int l, r, k;
} s[N << 2], t[N << 2];
int to[N << 2];

struct BIT{
    int val[N];
    #define lb(x) (x & (-x))
    stack<tuple<int, int>> q;
    void add(int x, int k){
        for(int i = x; i <= n; i += lb(i)) val[i] += k;
        q.push({x, k});
    }
    int qur(int x){
        int res = 0;
        for(int i = x; i; i -= lb(i)) res += val[i];
        return res;
    }
    int sum(int l, int r){
        return qur(r) - qur(l - 1);
    }
    void init(){
        while(q.size()){
            auto [x, vv] = q.top(); q.pop();
            for(int i = x; i <= n; i += lb(i)) val[i] -= vv;
        }
    }
} bit, cnt;

void solve(int l, int r, int ql, int qr){

    if(l == r){
        for(int i = ql; i <= qr; i ++){
            if(l == 0) s[i].ans = -1;
            else s[i].ans += s[i].k / l + (s[i].k % l > 0);
        }
        return;
    }

    int mid = (l + r) >> 1;

    bit.init();
    cnt.init();

    int cl = 0, cr = 0;
    for(int i = ql; i <= qr; i ++){
        if(s[i].opt == 1){
            if(abs(s[i].x) > mid){
                bit.add(s[i].c, s[i].x), cr ++, to[i] = 2;
                cnt.add(s[i].c, s[i].x / abs(s[i].x));
            }
            else cl ++, to[i] = 1;
        }
        else{
            int S = bit.sum(s[i].l, s[i].r);
            if(S >= s[i].k) cr ++, to[i] = 2;
            else cl ++, to[i] = 1, s[i].k -= S, s[i].ans += cnt.sum(s[i].l, s[i].r);
        }

    }

    int u = ql, v = ql + cl;
    for(int i = ql; i <= qr; i ++){
        if(to[i] == 1) t[u ++] = s[i];
        else t[v ++] = s[i];
    }
    for(int i = ql; i <= qr; i ++) s[i] = t[i];

    if(cl) solve(l, mid, ql, ql + cl - 1);
    if(cr) solve(mid + 1, r, ql + cl, qr);

}

signed main(){
    ios::sync_with_stdio(0), cin.tie(0);

    cin >> n >> q;
    for(int i = 1; i <= n; i ++){
        cin >> a[i]; m ++;
        s[m] = {1, m, 0, i, a[i], 0, 0, 0};
    }
    for(int i = 1; i <= q; i ++){
        int c, x, l, r, k;
        cin >> c >> x >> l >> r >> k;
        m ++; s[m] = {1, m, 0, c, -a[c], 0, 0, 0};
        a[c] = x;
        m ++; s[m] = {1, m, 0, c, a[c], 0, 0, 0};
        m ++; s[m] = {2, m, 0, 0, 0, l, r, k};
    }

    solve(0, 1e9, 1, m);
    sort(s + 1, s + m + 1, [](Event a, Event b){
        return a.id < b.id;
    });
    for(int i = 1; i <= m; i ++){
        if(s[i].opt == 2) cout << s[i].ans << "\n";
    }

    return 0;
}