「NOIP十连赛day3」序列 - 线段树

题目大意

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

---

题目分析

看起来很难做，官方题解似乎用的主席树，可以做到$O(n\log n)$。
然而对于$10^5$的数据范围，$O(n\log^2 n)$的复杂度是完全可以接受的。

我们可以对询问建立线段树，处理区间内对答案的贡献，然后向上传递贡献。

对于每次对值的修改，在线段树中找到对应区间（叶子节点），然后将路径上的贡献全部修改即可。

---

代码

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
inline const int Get_Int() {
	int num=0,bj=1;
	char x=getchar();
	while(x<'0'||x>'9') {
		if(x=='-')bj=-1;
		x=getchar();
	}
	while(x>='0'&&x<='9') {
		num=num*10+x-'0';
		x=getchar();
	}
	return num*bj;
}
const int maxn=100005;
struct Query {
	int l,r,x;
	bool operator < (const Query& b) const {
		return x<b.x;
	}
} Q[maxn];
int Val[maxn];
struct Tree {
	int left,right,val,sum;
	vector<int>Ask;
};
struct Segment_Tree {
	Tree tree[maxn*4];
	#define ls index<<1
	#define rs index<<1|1
	void build(int index,int Left,int Right) {
		tree[index].left=Left,tree[index].right=Right;
		if(Left==Right)return;
		int mid=(Left+Right)>>1;
		build(ls,Left,mid);
		build(rs,mid+1,Right);
	}
	void push_up(int index) {
		tree[index].sum=tree[ls].sum+tree[rs].sum+tree[index].val;
	}
	void insert(int index,int Left,int Right,int x) {
		if(Right<tree[index].left||Left>tree[index].right)return;
		if(Left<=tree[index].left&&Right>=tree[index].right) {
			tree[index].Ask.push_back(x);
			return;
		}
		insert(ls,Left,Right,x);
		insert(rs,Left,Right,x);
	}
	void modify(int index,int target,int val) {
		if(target<tree[index].left||target>tree[index].right)return;
		tree[index].val-=upper_bound(tree[index].Ask.begin(),tree[index].Ask.end(),Val[target])-tree[index].Ask.begin();
		if(tree[index].left==tree[index].right) {
			tree[index].val+=upper_bound(tree[index].Ask.begin(),tree[index].Ask.end(),val)-tree[index].Ask.begin();
			Val[target]=val;
			tree[index].sum=tree[index].val;
			return;
		}
		modify(ls,target,val);
		modify(rs,target,val);
		tree[index].val+=upper_bound(tree[index].Ask.begin(),tree[index].Ask.end(),val)-tree[index].Ask.begin();
		push_up(index);
	}
} st;
int n,m,q,a[maxn],lastans=0;
int main() {
	n=Get_Int();
	m=Get_Int();
	q=Get_Int();
	for(int i=1; i<=n; i++)a[i]=Get_Int();
	for(int i=1; i<=m; i++) {
		Q[i].l=Get_Int();
		Q[i].r=Get_Int();
		Q[i].x=Get_Int();
	}
	sort(Q+1,Q+m+1);
	memset(Val,-0x3f,sizeof(Val));
	st.build(1,1,n);
	for(int i=1; i<=m; i++)st.insert(1,Q[i].l,Q[i].r,Q[i].x);
	for(int i=1; i<=n; i++)st.modify(1,i,a[i]);
	printf("%d\n",lastans=st.tree[1].sum);
	for(int i=1; i<=q; i++) {
		int p=Get_Int()^lastans,v=Get_Int()^lastans;
		st.modify(1,p,v);
		printf("%d\n",lastans=st.tree[1].sum);
	}
	return 0;
}