您的位置: 首页  >  IT文章  >  [CSP-S模拟测试]:序列（主席树）

[CSP-S模拟测试]:序列（主席树）

分类: IT文章 • 2022-08-03 22:00:57

题目描述

小$A$把自己之前得到的序列展示给了小$B$，不过这一次，他并不要求小$B$模仿他之前的行为。他给了小$B$一些询问，每个询问都是$l r x$的形式，要求小$B$数出在序列的第$l$个到第$r$个元素中有多少是不小于$x$的。小$B$很快就算出来了。小$A$很不甘心，于是要求动态修改这个序列......这样，他只要求每次修改后求出所有询问答案的和即可。然而小$B$还是很快就算出来了，小$A$很生气，于是把问题抛给了你。

输入格式

由于一些原因，本题采取一定的方式加密了修改操作。
第一行三个整数$n m q$，分别表示序列长度、询问个数和修改次数。第二行$n$个正整数描述序列。接下来$m$行每行三个数$l r x$，表示一次询问。最后$q$行每行两个数$p v$，表示把$p ext{^}lastans$这个位置上的数修改成$v ext{^}lastans$（其中$lastans$指上次修改之后的答案，初始即为没有修改过的原序列的询问答案，$ ext{^}$为异或符号，$C/C++$中为$ ext{^}$，$pascal$中为$xor$）。

输出格式

$q+1$行每行一个整数，第一行表示原序列的所有询问答案之和，后面$q$行表示每次修改之后的序列的所有询问答案之和。

样例

样例输入：

4 2 2
1 4 2 3
2 4 3
1 3 2
6 6
2 7

样例输出：

4
3
4

数据范围与提示

对于$20\%$的数据，$n,m,qleqslant 100$
对于$40\%$的数据，$n,m,qleqslant 1,000$
对于$100\%$的数据，$n,m,qleqslant 100,000$，序列中的数（包括修改后的）
均为正数且不超过$n$，保证数据合法。

题解

先来考虑如何优化暴力，我们每改变一个点，这个点只会给包含它的区间做贡献。

那么，我们考虑如何快速求出每一个点对答案的贡献。

考虑主席树，对于每一个点建立一棵主席树，点的编号为$x$，对于询问的$l$，我们将其$x$点点权$+1$；对于询问的$r$，我们将点$r+1$的$x$点$-1$，表示删掉了这个询问。

预处理的过程只需要继承上一个点的树即可。

对于修改，我们可以先计算出来原来的贡献，将其减去；再计算现在的贡献，加上去即可。

时间复杂度：$Theta((q+n)log m)$。

期望得分：$100$分。

实际得分：$100$分。

代码时刻

#include<bits/stdc++.h>
using namespace std;
int n,m,q;
int a[100001];
int root[100001],tr[4000000],ls[4000000],rs[4000000],cnt;
long long ans;
vector<pair<int,int> > question[100001];
void add(int &x,int pre,int l,int r,int w,int k)
{
	x=++cnt;
	if(l==r)
	{
		tr[x]=tr[pre]+k;
		return;
	}
	int mid=(l+r)>>1;
	if(w<=mid)
	{
		add(ls[x],ls[pre],l,mid,w,k);
		rs[x]=rs[pre];
	}
	else
	{
		add(rs[x],rs[pre],mid+1,r,w,k);
		ls[x]=ls[pre];
	}
	tr[x]=tr[ls[x]]+tr[rs[x]];
}
int ask(int x,int l,int r,int L,int R)
{
	if(r<L||R<l)return 0;
	if(L<=l&&r<=R)return tr[x];
	int mid=(l+r)>>1;
	return ask(ls[x],l,mid,L,R)+ask(rs[x],mid+1,r,L,R);
}
int main()
{
	scanf("%d%d%d",&n,&m,&q);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	for(int i=1;i<=m;i++)
	{
		int l,r,x;
		scanf("%d%d%d",&l,&r,&x);
		question[l].push_back(make_pair(x,1));
		question[r+1].push_back(make_pair(x,-1));
	}
	for(int i=1;i<=n;i++)
	{
		root[i]=root[i-1];
		for(int j=0;j<question[i].size();j++)
			add(root[i],root[i],0,n,question[i][j].first,question[i][j].second);
		ans+=ask(root[i],0,n,0,a[i]);
	}
	printf("%lld
",ans);
	while(q--)
	{
		int p,v;scanf("%d%d",&p,&v);
		p^=ans;v^=ans;
		ans-=ask(root[p],0,n,0,a[p]);
		ans+=ask(root[p],0,n,0,v);
		a[p]=v;
		printf("%lld
",ans);
	}
	return 0;
}

rp++

相关推荐