题解：P9388 [THUPC 2023 决赛] 先人类的人类选别

· · 题解

需要观察。

可以注意到做一次操作，相当于将一个数加入，然后将一个最小的数移除。这便于统计操作后的和。进一步观察到修改操作的相似性：他们都从 1 开始进行；甚至可以发现任意调换修改顺序，最后的数列不变。

那么对于一个数列大小为 siz，从开头起进行若干次操作后，最后剩的就是数列中的数和操作的数的前 siz 大。这是容易维护的。

根据性质，容易想到将所有操作的数打包起来维护；将 [l, r] 的询问转化为 [1, r], [1,l-1] 两段以 1 开头的区间，就转化为上述问题了。将操作用值域线段树维护，数组用主席树维护，用线段树二分求前 k 大数的和就可以了。

#include <bits/stdc++.h>
using namespace std;

int n, m, a;
struct Chairman_Tree{
    int tot, root[500002];
    struct Node {
        int lson, rson;
        long long sum;
        int siz;
    }t[10000002];
    void Add(int lroot,int pos,int l,int r,int tar){
        t[pos] = t[lroot];
        if(l == r){
            t[pos].siz++;
            t[pos].sum += l;
            return;
        }
        int mid = (l + r) >> 1;
        if(tar <= mid){
            t[pos].lson = ++tot;
            Add(t[lroot].lson, t[pos].lson, l, mid, tar);
        }
        else {
            t[pos].rson = ++tot;
            Add(t[lroot].rson, t[pos].rson, mid+1, r, tar);
        }
        t[pos].siz = t[t[pos].lson].siz + t[t[pos].rson].siz;
        t[pos].sum = t[t[pos].lson].sum + t[t[pos].rson].sum;
    }
};
Chairman_Tree C;

#define l(pos) pos << 1
#define r(pos) (pos << 1) | 1
struct Segment_Tree{
    long long sum[2000002];
    int siz[2000002];
    void Add(int pos,int l,int r,int tar){
        if(l == r){
            siz[pos]++;
            sum[pos] += l;
            return;
        }
        int mid = (l + r) >> 1;
        if(tar <= mid){
            Add(l(pos), l, mid, tar);
        }
        else {
            Add(r(pos), mid+1, r, tar);
        }
        siz[pos] = siz[l(pos)] + siz[r(pos)];
        sum[pos] = sum[l(pos)] + sum[r(pos)];
    }
};
Segment_Tree T;

long long Solve(int pos1,int pos2,int l,int r,int k){
    if(l == r){
        return 1ll * k * l;
    }
    int mid = (l + r) >> 1, S = T.siz[r(pos1)] + C.t[C.t[pos2].rson].siz;
    if(k <= S) return Solve(r(pos1), C.t[pos2].rson, mid+1, r, k);
    else return T.sum[r(pos1)] + C.t[C.t[pos2].rson].sum + Solve(l(pos1), C.t[pos2].lson, l, mid, k - S);
}

int main(){

    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d",&a);
        C.tot++, C.root[i] = C.tot;
        C.Add(C.root[i-1], C.root[i], 1, n, a);
    }

    while(m--){
        int l, r, x;
        scanf("%d%d%d",&x,&l,&r);
        T.Add(1, 1, n, x);
        printf("%lld\n",Solve(1, C.root[r], 1, n, r) - Solve(1, C.root[l-1], 1, n, l-1));
    }

    return 0;
}