Wannafly Winter Camp Day5 Div1 C题 Division 主席树

（有任何问题欢迎留言或私聊 && 欢迎交流讨论哦

Catalog

Problem：传送门

 原题目描述在最下面。
 长度为$n$n的序列，$q$q次查询，查询区间$[l,r]$[l,r]经过$k$k次操作后区间和最小是多少？（每次操作选择一个数把它坎一半）

Solution：

调$bug$bug调到死。。。

感谢群里一位大佬的帮助orz

一个数字经过$log$log次操作后肯定会变成$0$0。
如果内存充足，你可以把所有过程中产生了$nlog(n)$nlog(n)个贡献插入到主席树里面，然后查询前$k$k大的和就行了。
然后用区间所有值的和 减去 这些数字中前$k$k大得和就是答案。

但是很明显，它肯定不会让你这么简单就写完的。
$dls$dls给你了$256M$256M的空间！$256!!!$256!!!

考虑一个优化，对于每个区间我们要取得是那些数字前$k$k大的和。

我们把所有的数字分到$2^k-2^{k+1}$2k−2k+1分别做。
把询问离散化下来，从大到小枚举$k$k，每次只把属于$[2^k,2^{k+1}]$[2k,2k+1]的数字插入主席树，每次查询前$k'$k′的数字之和。
还有一个优化就是如果区间$[l,r]$[l,r]插入主席树的数的个数小于$k'$k′，可以用前缀和优化掉这一部分。
记住每次结束后把插到主席树中去的数字除$2$2。

AC_Code：

#include<bits/stdc++.h>
#define fi first
#define se second
#define iis std::ios::sync_with_stdio(false)
#define pb push_back
#define o2(x) (x)*(x)
using namespace std;
typedef long long LL;
typedef pair<int, LL> pii;

const int MXN = 1e6 + 6;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
int n, q;
int ar[MXN], num[MXN];
LL sum[MXN];
struct QUERY {
    int l, r, k;
    LL ans;
}cw[MXN];
struct lp {
    int l, r, cnt;
    LL sum;
}node[MXN*16];
int inde, Root[MXN];
void z_update(int old, int &cur, int val, LL L, LL R) {
    cur = ++ inde;
    node[cur] = node[old];
    if(L == R) {
        node[cur].sum += val - val/2;
        ++ node[cur].cnt;
        return;
    }
    LL mid = (L + R) / 2;
    if(val <= mid) z_update(node[old].l, node[cur].l, val, L, mid);
    else z_update(node[old].r, node[cur].r, val, mid+1, R);
    node[cur].sum = node[node[cur].l].sum + node[node[cur].r].sum;
    node[cur].cnt = node[node[cur].l].cnt + node[node[cur].r].cnt;
}
LL z_query(int k, int old, int cur, LL L, LL R) {
    if(L == R) {
        return (LL)k*(L-L/2);//权值为L产生的贡献是k*(L-L/2)
    }
    LL mid = (L + R) / 2;
    int tmp = node[node[cur].r].cnt - node[node[old].r].cnt;
    if(k <= tmp) {
        return z_query(k, node[old].r, node[cur].r, mid + 1, R);
    }else {
        return node[node[cur].r].sum - node[node[old].r].sum
        + z_query(k-tmp, node[old].l, node[cur].l, L, mid);
    }
}
/*LL query(int k, int old, int cur, int L, LL R) {
    printf("%d %lld %lld\n", k, node[cur].sum, node[old].sum);
    if(L == R) {
        printf("*%d %d\n", L,k*(L-L/2));
        return (LL)k*(L-L/2);
    }
    LL mid = (L + R) / 2;
    int tmp = node[node[cur].r].cnt - node[node[old].r].cnt;
    printf("%d %d %d %d %lld\n", k, tmp, node[node[old].r].cnt,node[node[cur].r].cnt,node[node[cur].r].sum - node[node[old].r].sum);
    if(k <= tmp) {
        return query(k, node[old].r, node[cur].r, mid + 1, R);
    }else {
        return node[node[cur].r].sum - node[node[old].r].sum
        + query(k-tmp, node[old].l, node[cur].l, L, mid);
    }
}*/
int main(){
    scanf("%d%d", &n, &q);
    for(int i = 1; i <= n; ++i) scanf("%d", ar+i), sum[i]=sum[i-1]+ar[i];
    for(int i = 1; i <= q; ++i) {
        scanf("%d%d%d", &cw[i].l, &cw[i].r, &cw[i].k);
        cw[i].ans = sum[cw[i].r] - sum[cw[i].l-1];
    }
    LL L, R;
    for(int T = 30; T >= 0; --T) {
        L = 1LL<<T, R = 2LL<<T, inde = 0;
        node[0].l = node[0].r = node[0].sum = node[0].cnt = 0;
        for(int i = 1; i <= n; ++i) if(ar[i]>>T&1) {
            z_update(Root[i-1], Root[i], ar[i], L, R);
            //if(T == 2) printf("[%d %d]\n", i, ar[i]);
            sum[i] = sum[i-1] + ar[i] - ar[i]/2; num[i] = num[i-1] + 1;
        }else Root[i] = Root[i-1], sum[i] = sum[i-1], num[i] = num[i-1];
        //printf("T = %d\n", T);
        for(int i = 1, tmp; i <= q; ++i) {
            if(cw[i].k == 0) continue;
            if(cw[i].k >= num[cw[i].r] - num[cw[i].l-1]) {
                cw[i].k -= num[cw[i].r] - num[cw[i].l-1];
                cw[i].ans -= sum[cw[i].r] - sum[cw[i].l-1];
            }else {
                //printf("*%lld %d ", cw[i].ans, cw[i].k);
                cw[i].ans -= z_query(cw[i].k, Root[cw[i].l-1], Root[cw[i].r], L, R);
                //printf("%lld %d\n", cw[i].ans, T);
                cw[i].k = 0;
            }
            //printf("%d %d %d\n", cw[i].l, cw[i].r, cw[i].k);
        }
        for(int i = 1; i <= n; ++i) if(ar[i]>>T&1) ar[i] >>= 1;
        //printf("***\n");
    }
    for(int i = 1; i <= q; ++i) printf("%lld\n", cw[i].ans);
    return 0;
}

Problem Description：