[CSP-S模拟测试]:大新闻（主席树）

题目传送门（内部题20）

输入格式

第一行为两个数$n,m$，意义如题所述。
接下来一行$n$个数，代表一开始$n$条大新闻的$naive$值。
接下来$m$行，每行一个操作，输入格式如下：
读入$1$，代表第一种事件。
读入$2,x$，代表第二种事件。
读入$3,l,r,k$，代表第三种事件。

输出格式

对于每一个第三种事件输出一行整数，代表答案

样例

样例输入：

6 8
2 7 4 3 5 9
3 2 5 3
1
2 4
3 1 4 2
2 6
3 1 7 5
1
3 3 6 4

样例输出：

5
4
6
9

数据范围与提示

样例解释：

初始序列为$2,7,4,3,5,9$。
询问$7,4,3,5$的第$3$小值，答案为$5$。
操作后序列变成$7,4,3,5,9$。
操作后序列变成$4,7,4,3,5,9$。
询问$4,7,4,3$的第$2$小值，答案为$4$。
操作后序列变成$6,4,7,4,3,5,9$。
询问序列$6,4,7,4,3,5,9$的第$5$小值，答案为$6$。
操作后序列变成$4,7,4,3,5,9$。
询问序列$4,3,5,9$的第$4$小值，答案为$9$。

数据范围：

对于$30\%$的数据，满足$1\leqslant n,m\leqslant 2,000$。
对于$50\%$的数据，满足$1\leqslant n,m\leqslant 30,000$。
对于$70\%$的数据，满足$1\leqslant n,m\leqslant 80,000$。
对于$100\%$的数据，满足$1\leqslant n,m\leqslant 2\times 10^5$。
保证数据合法，当没有新闻时不存在删除操作。
保证$1\leqslant naive$值$\leqslant 10^9$，保证$1\leqslant l\leqslant r\leqslant $当前新闻数，$k\leqslant r−l+1$。

题解

观察数据范围和操作，发现是主席树板子题（然而并不会打……）。

不会的先学一下主席树吧。

正解直接用的树上差分，少个$\log$。

时间复杂度：$(n+m)\log^2n$。

期望得分：$100$分。

实际得分：$100$分。

代码时刻

#include<bits/stdc++.h>

using namespace std;

int n,m;

int a[200001],root[500000],tot;

int trsum[10000001],lson[10000001],rson[10000001];

void insert(int &x,int pre,int l,int r,int w)

{

	x=++tot;

	trsum[x]=trsum[pre]+1;

	lson[x]=lson[pre];

	rson[x]=rson[pre];

	if(l==r)return;

	int mid=(l+r)>>1;

	if(w<=mid)insert(lson[x],lson[pre],l,mid,w);

	else insert(rson[x],rson[pre],mid+1,r,w);

}

int ask(int x,int pre,int l,int r,int k)

{

	if(l==r)return l;

	int mid=(l+r)>>1;

	if(trsum[lson[x]]-trsum[lson[pre]]>=k)return ask(lson[x],lson[pre],l,mid,k);

	else return ask(rson[x],rson[pre],mid+1,r,k-trsum[lson[x]]+trsum[lson[pre]]);

}

int main()

{

	scanf("%d%d",&n,&m);

	for(int i=n;i;i--)

		scanf("%d",&a[i]);

	for(int i=1;i<=n;i++)

		insert(root[i],root[i-1],1,1<<30,a[i]);

	while(m--)

	{

		int opt;

		scanf("%d",&opt);

		switch(opt)

		{

			case 1:n--;break;

			case 2:

				int x;

				scanf("%d",&x);

				n++;

				insert(root[n],root[n-1],1,1<<30,x);

				break;

			case 3:

				int l,r,k;

				scanf("%d%d%d",&l,&r,&k);

				printf("%d\n",ask(root[n-l+1],root[n-r],1,1<<30,k));

				break;

		}

	}

	return 0;

}

rp++

巴特西