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

dyc2022 · 2025-12-12 19:12:35 · 题解

更好的阅读体验

考虑差分一下，变成查询一个前缀的和。操作是从左往右做的，所以很好。

经过简单的模拟可以发现，对一个前缀进行一次 x 的操作，也就是将 x 扔到前缀里面，然后把最小值扔掉。为啥要扔掉一个最小值？我们扔掉的数就是完成操作之后的 x。

从这里我们可以看出，对于一个特定的前缀 i，你把 x 一个一个塞进去，塞一个扔一个的作用效果，其实和塞 q 个扔 q 个的作用效果一样，因为实际上我们不关心顺序。所以假设我们进行到第 j 次操作，前 j 次操作的 x 分别是 x_1 \sim x_j，那么我们做的事情其实是维护一个可重集，将 a_1 \sim a_i 扔进去，把 x_1 \sim x_j 扔进去，最后把前 j 小的扔掉。

我们要找一个前缀和一个 x 的可重集合并起来，前 j 小的和，不难想到权值线段树加主席树。

具体地，我们对静态的 a 序列维护主席树，对不断加入的 x 维护权值线段树。查询的时候，我们把某一个前缀对应的版本树和这个权值线段树加在一起，然后二分求前 i 小和即可。

复杂度 O(n \log n)，完全不卡常。

#include<bits/stdc++.h>
#define endl '\n'
#define N 500006
using namespace std;
using i64=long long;
int n,q,tot,root,rt[N];
i64 s[N];
struct Node {int sz,ls,rs; i64 sum;} tree[N<<6];
void update(int &p,int q,int l,int r,int k)
{
    tree[p=++tot]=tree[q];
    tree[p].sz++,tree[p].sum+=k; if(l==r)return;
    int mid=l+r>>1; k<=mid?update(tree[p].ls,tree[q].ls,l,mid,k):
                           update(tree[p].rs,tree[q].rs,mid+1,r,k);
}
void update(int &p,int l,int r,int k)
{
    if(!p)p=++tot; tree[p].sz++,tree[p].sum+=k; if(l==r)return;
    int mid=l+r>>1; k<=mid?update(tree[p].ls,l,mid,k):
                           update(tree[p].rs,mid+1,r,k);
}
i64 query(int p,int q,int l,int r,int k)
{
    if(l==r)return 1ll*l*k;
    int mid=l+r>>1;
    int lsz=tree[tree[p].ls].sz+tree[tree[q].ls].sz;
    i64 lsum=tree[tree[p].ls].sum+tree[tree[q].ls].sum;
    if(lsz>=k)return query(tree[p].ls,tree[q].ls,l,mid,k);
    return lsum+query(tree[p].rs,tree[q].rs,mid+1,r,k-lsz);
}
main()
{
    scanf("%d%d",&n,&q);
    for(int i=1,x;i<=n;i++)
        scanf("%d",&x),update(rt[i],rt[i-1],1,n,x),s[i]=s[i-1]+x;
    for(int i=1,x,l,r;i<=q;i++)
    {
        scanf("%d%d%d",&x,&l,&r),update(root,1,n,x);
        printf("%lld\n",s[r]-s[l-1]-query(rt[r],root,1,n,i)+query(rt[l-1],root,1,n,i));
    }
    return 0;
}