题解：AT_abc467_g [ABC467G] Many Sweets Problem

· · 题解

题意：从区间 [L,R] 选取最少的元素使得和不小于 k，带单点修改。

显然贪心优先都选大的。

问题转化为：区间 [L,R] 前 m 大元素之和不小于 k 的最小 m。

考虑使用树套树。

外层 BIT 维护位置前缀。

内层权值线段树维护值域上的元素个数以及和。

离散化修改啥的都是板子这里就不写了。

直接写查询。

首先我们要提取区间内对应的线段树的根节点。

lenr = lenl = 0;
    for (int i = r; i; i -= i & -i) rlst[lenr++] = root[i];
    for (int i = l - 1; i; i -= i & -i) llst[lenl++] = root[i];
    ll tot = 0;

然后要判一个无解，就是整段区间内和都小于 k，就返回 -1。

然后开始二分加贪心。

优先检查右子树：如果右子树和大于等于 k，说明只要在右子树里面选元素，直接进入。
如果不行那么就要把整个右子树都拿走，然后剩余的进入左子树。

如果到达了叶子节点，那么直接计算，需要 \lceil \frac{k}{v}\rceil 个元素。

不明白的看代码，马蜂比较正常。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAXN = 5e5+10, MAXV = 5e5+10, SEGN = 5e7+5;
struct Node {
    int lc, rc, cnt;
    ll sum;
} tree[SEGN];
int tot;
int n, q, M, V;
ll a[MAXN];
ll vl[MAXV];
int root[MAXN];
int ca[MAXN], xa[MAXN], la[MAXN], ra[MAXN];
ll ka[MAXN];
int rlst[35], llst[35], lenr, lenl, tmpr[35], tmpl[35];
int new_node() {
    ++tot;
    tree[tot] = {0, 0, 0, 0};
    return tot;
}
void seg_add(int &rt, int l, int r, int pos, int d, ll val) {
    if (!rt) rt = new_node();
    tree[rt].cnt += d;
    tree[rt].sum += d * val;
    if (l == r) return;
    int mid = l + r >> 1;
    if (pos <= mid)
        seg_add(tree[rt].lc, l, mid, pos, d, val);
    else
        seg_add(tree[rt].rc, mid + 1, r, pos, d, val);
}
void bit_add(int idx, int pos, int d, ll val) {
    for (int i = idx; i <= n; i += i & -i)
        seg_add(root[i], 1, M, pos, d, val);
}

//以上为树套树板子 

int query(int l, int r, ll k) {
    lenr = lenl = 0;
    for (int i = r; i; i -= i & -i) rlst[lenr++] = root[i];
    for (int i = l - 1; i; i -= i & -i) llst[lenl++] = root[i];//提取根编号
    ll tot = 0;
    for (int i = 0; i < lenr; i++) tot += tree[rlst[i]].sum;
    for (int i = 0; i < lenl; i++) tot -= tree[llst[i]].sum;//计算和
    if (tot < k) return -1;
    int ans = 0, vL = 1, vR = M;
    while (vL < vR) {
        int mid = (vL + vR) >> 1;
        ll rsum = 0;
        int rcnt = 0;
        for (int i = 0; i < lenr; i++) {
            int rc = tree[rlst[i]].rc;
            if (rc) rsum += tree[rc].sum, rcnt += tree[rc].cnt; 
        }
        for (int i = 0; i < lenl; i++) {
            int rc = tree[llst[i]].rc;
            if (rc) rsum -= tree[rc].sum, rcnt -= tree[rc].cnt; 
        }
        if (rsum >= k) {//右子树大于等于 k 
            int tR = 0, tL = 0;
            for (int i = 0; i < lenr; i++) {
                int rc = tree[rlst[i]].rc;
                if (rc) tmpr[tR++] = rc;
            }
            for (int i = 0; i < lenl; i++) {
                int rc = tree[llst[i]].rc;
                if (rc) tmpl[tL++] = rc;
            }
            copy(tmpr, tmpr + tR, rlst), lenr = tR;
            copy(tmpl, tmpl + tL, llst), lenl = tL;
            vL = mid + 1;//通过复制线段树根编号进入右子树 
        } else {//需要左子树 
            k -= rsum;//注意要减去右子树 
            ans += rcnt;
            int tR = 0, tL = 0;
            for (int i = 0; i < lenr; i++) {
                int lc = tree[rlst[i]].lc;
                if (lc) tmpr[tR++] = lc;
            }
            for (int i = 0; i < lenl; i++) {
                int lc = tree[llst[i]].lc;
                if (lc) tmpl[tL++] = lc;
            }
            copy(tmpr, tmpr + tR, rlst), lenr = tR;
            copy(tmpl, tmpl + tL, llst), lenl = tL;
            vR = mid;//同右子树
        }
    }
    ll lvl = vl[vL];
    ans += (k + lvl - 1) / lvl;//叶子节点 
    return ans;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> q;
    V = 0;
    for (int i = 1; i <= n; i++) cin >> a[i], vl[++V] = a[i];
    for (int i = 1; i <= q; i++) cin >> ca[i] >> xa[i] >> la[i] >> ra[i] >> ka[i], vl[++V] = xa[i];

    //离散化&添加节点 
    sort(vl + 1, vl + V + 1);
    M = unique(vl + 1, vl + V + 1) - vl - 1;
    for (int i = 1; i <= n; i++) {
        int pos = lower_bound(vl + 1, vl + M + 1, a[i]) - vl;
        bit_add(i, pos, 1, a[i]);
    }

    for (int i = 1; i <= q; i++) {
        int c = ca[i], x = xa[i], l = la[i], r = ra[i];
        ll k = ka[i];
        int opos = lower_bound(vl + 1, vl + M + 1, a[c]) - vl;
        bit_add(c, opos, -1, a[c]);//删除原来的 
        a[c] = x;
        int npos = lower_bound(vl + 1, vl + M + 1, x) - vl;//添加 
        bit_add(c, npos, 1, x);
        cout << query(l, r, k) << "\n";//查询 
    }
    return 0;
}