【bzoj 十连测】[noip2016十连测第三场]Problem C: 序列（静态主席树）

Problem C: [noip2016十连测第三场]序列

Time Limit: 10 Sec Memory Limit: 256 MB
Submit: 78 Solved: 32
[ Submit][ Status][ Web Board]

Description

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

Input

由于一些原因，本题采取一定的方式加密了修改操作。第一行三个整数nmq，分别表示序列长度、询问个数和修改次数。第二行n个正整数描述序列。接下来m行每行三个数lrx，表示一次询问。最后q行每行两个数pv，表示把p^la stans这个位置上的数修改成v^lastans（其中lastans指上次修改之后的答案，初始即为没有修改过的原序列的询问答案，^为异或符号，C/C++中为^，pascal中为xor）。
【数据范围与约定】
对于 20%的数据， n,m,q≤100
对于 40%的数据， n,m,q≤1000
对于 100%的数据， n,m,q≤100000，序列中的数（包括修改后的）
均为正数且不超过 n，保证数据合法。

Output

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

Sample Input

Sample Output

4 
3 
4

HINT

【题解】【静态主席树+前缀和维护】
【NOIP考主席树。。。hehehe】
【先建一棵主席树，外层以每个位置为根的标号建树，内层权值线段树，首次询问时在[root[l] - root[r] ]里查询[x,n]】
【然后重新建树，外层以每次询问的x为根的标号建树，内层维护有多少个包含当前点的区间，前缀和维护，查询时，如果原数小于当前要更改为的元素，那么要加上中间这一段的答案；反之，要减去中间差的这一段的答案】

#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
struct node{
	int Left,Right;
	ll num;
}tree[5000010];
struct question{
	int qL,qR,k;
}que[100010];
ll ans;
int a[100010],root[100010];
int n,m,q,sz;

int tmp(question a,question b)
{
	return a.k<b.k;
}

void build(int &now,int l,int r,int x)
{
	tree[++sz]=tree[now]; now=sz;
	tree[now].num++;
	if(l==r) return;
	int mid=(l+r)>>1;
	if(x<=mid) build(tree[now].Left,l,mid,x);
	if(x>mid) build(tree[now].Right,mid+1,r,x);
}
ll ask(int x,int y,int l,int r,int al,int ar)
{
	if(al<=l&&r<=ar) return tree[y].num-tree[x].num;
	int mid=(l+r)>>1;
	ll sum=0;
	if(al<=mid) sum+=ask(tree[x].Left,tree[y].Left,l,mid,al,ar);
	if(ar>mid) sum+=ask(tree[x].Right,tree[y].Right,mid+1,r,al,ar);
	return sum;
}

void rebuild(int&now,int l,int r,int top,int al,int ar,int opt)
{
	if(!opt||now<top) tree[++sz]=tree[now],now=sz;
	if(al<=l&&r<=ar) {tree[now].num++; return;}
	int mid=(l+r)>>1;
	if(al<=mid) rebuild(tree[now].Left,l,mid,top,al,ar,opt);
	if(ar>mid) rebuild(tree[now].Right,mid+1,r,top,al,ar,opt);
}
ll query(int x,int y,int l,int r,int val)
{
	if(l==r) return tree[y].num-tree[x].num;
	int mid=(l+r)>>1;
	ll sum=tree[y].num-tree[x].num;
	if(val<=mid) sum+=query(tree[x].Left,tree[y].Left,l,mid,val);
	if(val>mid) sum+=query(tree[x].Right,tree[y].Right,mid+1,r,val);
	return sum;
}
int main()
{
    freopen("int.txt","r",stdin);
    freopen("my.txt","w",stdout);
	int i,j;
	scanf("%d%d%d",&n,&m,&q);
	for(i=1;i<=n;++i)
	 {
	 	scanf("%d",&a[i]);
	 	root[i]=root[i-1];
	 	build(root[i],1,n,a[i]);
	 }
	for(i=1;i<=m;++i)
	 {
	 	scanf("%d%d%d",&que[i].qL,&que[i].qR,&que[i].k);
	 	ans+=ask(root[que[i].qL-1],root[que[i].qR],1,n,que[i].k,n);
	 }
	printf("%lld\n",ans);
	sort(que+1,que+m+1,tmp);
	memset(tree,0,sizeof(tree));
	int t=1; sz=0;
	for(i=1;i<=n;++i)
	 {
	 	root[i]=root[i-1];
	 	j=t;
	 	if(que[t].k!=i) continue;
	 	rebuild(root[i],1,n,0,que[t].qL,que[t].qR,0);
		while(j<=m&&que[t].k==que[j].k) ++j;
	 	for(int l=t+1;l<j;++l) rebuild(root[i],1,n,root[i],que[l].qL,que[l].qR,1);
	 	if(j>m) break; t=j;
	 }
	for(i=que[m].k+1;i<=n;++i) root[i]=root[i-1];
	for(i=1;i<=q;++i)
	 {
	 	ll site,val;
	 	scanf("%lld%lld",&site,&val);
	 	site^=ans; val^=ans;
	 	if(a[site]<val) ans+=query(root[a[site]],root[val],1,n,site);
	 	if(a[site]>val) ans-=query(root[val],root[a[site]],1,n,site);
	 	a[site]=val;
	 	printf("%lld\n",ans);
	 }
	return 0;
	
}

秒客网