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

题目描述

小$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\text{^}lastans$这个位置上的数修改成$v\text{^}lastans$（其中$lastans$指上次修改之后的答案，初始即为没有修改过的原序列的询问答案，$\text{^}$为异或符号，$C/C++$中为$\text{^}$，$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,q\leqslant 100$
对于$40\%$的数据，$n,m,q\leqslant 1,000$
对于$100\%$的数据，$n,m,q\leqslant 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\n",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\n",ans);

	}

	return 0;

}

rp++

巴特西