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

需要观察。

可以注意到做一次操作，相当于将一个数加入，然后将一个最小的数移除。这便于统计操作后的和。进一步观察到修改操作的相似性：他们都从

1

开始进行；甚至可以发现任意调换修改顺序，最后的数列不变。

那么对于一个数列大小为

siz

，从开头起进行若干次操作后，最后剩的就是数列中的数和操作的数的前

siz

大。这是容易维护的。

根据性质，容易想到将所有操作的数打包起来维护；将

[l, r]

的询问转化为

[1, r], [1,l-1]

两段以

1

开头的区间，就转化为上述问题了。将操作用值域线段树维护，数组用主席树维护，用线段树二分求前

k

大数的和就可以了。

CPP

#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;
}

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

文章操作

相关推荐

评论

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