luogu3374

树状数组

不用看题目，就是一个标准的树状数组模板题目。
拿来作为CDQ分治的例题打，练练手！

#include<bits/stdc++.h>
using namespace std;
const int nm=2e6+10;
const int maxn=5e5+10;
struct node
{
	int t,type,v,pos;
	bool operator < (const node & a)const
	{
		if(pos!=a.pos)return pos<a.pos;
		if(type!=a.type)return type<a.type;
		if(t!=a.t)return t<a.t;
		return 0;
	}
}sz[nm],f[nm];
int n,m,cnt,js;
int ans[maxn];
void cdq(int l,int r)
{
	if(l==r)return ;
	int mid=(l+r)>>1;
	cdq(l,mid);
	cdq(mid+1,r);
	int q=l,h=mid+1,p=l,tp=0;
	while(q<=mid && h<=r)
	{
		if(sz[q]<sz[h])
		{
			f[p]=sz[q];
			if(sz[q].type==1)tp+=sz[q].v;
			++p;++q;
		}
		else
		{
			f[p]=sz[h];
			if(sz[h].type==2)ans[sz[h].v]-=tp;
			else if (sz[h].type==3)ans[sz[h].v]+=tp;
			++p;++h;
		}
	}
	while(q<=mid)
	{
		f[p]=sz[q];
		if(sz[q].type=1)tp+=sz[q].v;
		++p;++q;
	}
	while(h<=r)
	{
		f[p]=sz[h];
		if(sz[h].type==2)ans[sz[h].v]-=tp;
		else if (sz[h].type==3)ans[sz[h].v]+=tp;
		++p;++h;
	}
	for(int i=l;i<=r;++i)sz[i]=f[i];
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i)
	{
		scanf("%d",&sz[++cnt].v);
		sz[cnt].t=cnt;sz[cnt].type=1;sz[cnt].pos=i;
	}
	for(int op,x,y,i=1;i<=m;++i)
	{
		scanf("%d%d%d",&op,&x,&y);
		if(op==1)
		{
			sz[++cnt].v=y;sz[cnt].t=cnt;sz[cnt].type=1;sz[cnt].pos=x;
		}
		else
		{
			sz[++cnt].type=2;sz[cnt].t=cnt;sz[cnt].pos=x-1;sz[cnt].v=++js;
			sz[++cnt].type=3;sz[cnt].t=cnt;sz[cnt].pos=y;sz[cnt].v=js;
		}
	}
	cdq(1,cnt);
	for(int i=1;i<=js;++i)printf("%d
",ans[i]);
	return 0;
}