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

__FL__ · 2026-08-08 20:34:14 · 题解

一个重要的观察：第 i 次操作以后，前 j 个元素是 a_{1...j} 及 x_{1...i} 中的前 j 大。

证明显然，对于前 j 个元素而言，第 i 次操作会把 \min(x_i,a_{1...j}) 丢出去。

于是有转化：第 i 次操作后，\sum_{j=l}^r a_j = s_r-s_{l-1}，s 表示这次操作后的前缀和。

现在我们考虑怎么求原序列的一段前缀 和 操作序列的前 x 大的和。这是一个经典的线段树二分问题。对原序列建可持久化权值线段树，对操作序列单独建权值线段树，询问在两棵树上跑线段树二分。对对，和主席树板子题挺像的。

时间复杂度 O(n\log n)。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 500005;
int n,m,a[N],f[N<<5],rt[N],ls[N<<5],rs[N<<5],sz[N<<5],cnt,RT,sum[N];
int update(int nroot,int l,int r,int x)
{
    int root = ++cnt;
    f[root] = f[nroot],sz[root] = sz[nroot];
    f[root] += x;
    sz[root]++;
    if (l >= r) return root;
    int mid = (l+r)/2;
    if (x <= mid) ls[root] = update(ls[nroot],l,mid,x),rs[root] = rs[nroot];
    else rs[root] = update(rs[nroot],mid+1,r,x),ls[root] = ls[nroot];
    return root;
}
int updateq(int root,int l,int r,int x)
{
    if (!root) root = ++cnt;
    f[root] += x;
    sz[root]++;
    if (l >= r)
    {
        return root;
    }
    int mid = (l+r)/2;
    if (x <= mid) ls[root] = updateq(ls[root],l,mid,x);
    else rs[root] = updateq(rs[root],mid+1,r,x);
    return root;
}
int query(int root1,int root2,int l,int r,int k)
{
    if (l >= r) return k*l;
    int mid = (l+r)/2;
    if (sz[rs[root1]]+sz[rs[root2]] >= k) return query(rs[root1],rs[root2],mid+1,r,k);
    return f[rs[root1]]+f[rs[root2]]+query(ls[root1],ls[root2],l,mid,k-sz[rs[root1]]-sz[rs[root2]]);
}
signed main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        rt[i] = update(rt[i-1],1,n,a[i]);
    }
    for (int i = 1; i <= m; i++)
    {
        int x,l,r;
        cin >> x >> l >> r;
        RT = updateq(RT,1,n,x);
        cout << query(rt[r],RT,1,n,r)-query(rt[l-1],RT,1,n,l-1) << '\n';
    }
    return 0;
}