一直不会带根号的神奇的算法，今天看了一下论文PPT，总算看懂块状链表大致怎么弄了，然后才看了分块、莫队和块状树，感觉也不是很难。。

一、分块

基本的分块就是维护每个块内的信息，然后求的时候把散的和整块的分开来求救可以了

BZOJ2957维护块内单调性

#include<cstdio>
#include<algorithm>
const int BS=500,BN=200;
int i,n,m,x,y,p,b,ans,l,r,mid,top[BN+9];
double k,now,data[BN+9][BS+9],stack[BN+9][BS+9];
int main(){
	scanf("%d%d",&n,&m);
	while(m--){
		scanf("%d%d",&x,&y);k=(double)y/x;
		p=(x-1)%BS+1;b=(x-1)/BS+1;
		for(data[b][p]=k,top[b]=0,now=0,i=1;i<=BS;i++)
			if(data[b][i]>now)stack[b][++top[b]]=now=data[b][i];
		for(ans=0,now=0,i=1;i<=BN;i++){
			l=1;r=top[i];
			while(l<=r){
				mid=(l+r)>>1;
				if(now<stack[i][mid])r=mid-1;else l=mid+1;
			}
			ans+=top[i]-l+1;now=std::max(now,stack[i][top[i]]);
		}
		printf("%d\n",ans);
	}
}

BZOJ2141块套树状数组统计逆序对，MD竟然有相同的数 比树套树不知道高到哪里去了

#include<cstdio>
#include<algorithm>
using namespace std;
const int N=20010,BS=200,BN=100;
int n,m,i,bx,by,x,y,ans,top,c[BN+9][N],a[N];
struct EG{int x,z;}eg[N];
bool cmp(EG a,EG b){return a.x<b.x;}
void change(int w,int x,int z){for(;x<=n;x+=x&-x)c[w][x]+=z;}
int query(int w,int x){int tmp=0;for(;x;x-=x&-x)tmp+=c[w][x];return tmp;}
void go(int j){
	 if(a[j]<a[x])--ans;if(a[j]>a[x])++ans;  
     if(a[j]<a[y])++ans;if(a[j]>a[y])--ans;
}
int main(){
	scanf("%d",&n);
	for(i=1;i<=n;i++)scanf("%d",&eg[i].x),eg[i].z=i;
	sort(eg+1,eg+n+1,cmp);
	for(i=1;i<=n;i++){
		if(eg[i].x!=eg[i-1].x)++top;
        a[eg[i].z]=top;
    }
	for(i=n;i;i--)ans+=query(0,a[i]-1),change(0,a[i],1);
	for(i=1;i<=n;i++)change((i-1)/BS+1,a[i],1);
	printf("%d\n",ans);scanf("%d",&m);
	while(m--){
		scanf("%d%d",&x,&y);if(x>y)swap(x,y);
		bx=(x-1)/BS+1;by=(y-1)/BS+1;
		if(bx+1<=by-1){
			for(i=bx+1;i<by;i++){
				ans-=query(i,a[x]-1);ans+=query(i,n)-query(i,a[x]);
				ans+=query(i,a[y]-1);ans-=query(i,n)-query(i,a[y]);
			}
			for(i=x+1;i<=bx*BS;i++)go(i);
			for(i=by*BS-BS+1;i<y;i++)go(i);	
		}else for(i=x+1;i<y;i++)go(i);
		if(a[x]<a[y])ans++;if(a[x]>a[y])ans--;
		printf("%d\n",ans);change(bx,a[x],-1);change(by,a[y],-1);
		swap(a[x],a[y]);change(bx,a[x],1);change(by,a[y],1);
	}
}

BZOJ3295和上一题差不多，本来觉得可以水过，但谁知道这个是删除值不是删除位置，样例还看不出来。。觉得这么SB的题应该不会错，再看了遍题目才发现这个坑点。。

#include<cstdio>
const long long N=100010,BS=2000,BN=50;
long long n,m,ans,x,b,i,a[N],c[51][N],to[N];bool use[N];
long long min(long long x,long long y){return x<y?x:y;}
void change(long long w,long long x,long long z){for(;x<=n;x+=x&-x)c[w][x]+=z;}
long long query(long long w,long long x){long long tmp=0;for(;x;x-=x&-x)tmp+=c[w][x];return tmp;}
int main(){
	scanf("%lld%lld",&n,&m);
	for(i=1;i<=n;i++)scanf("%lld",&a[i]),to[a[i]]=i,ans+=query(0,n)-query(0,a[i]),change(0,a[i],1);
	for(i=1;i<=n;i++)change((i-1)/BS+1,a[i],1);
	while(m--){
		printf("%lld\n",ans);scanf("%lld",&x);
		x=to[x];b=(x-1)/BS+1;
		for(i=1;i<b;i++)ans-=query(i,n)-query(i,a[x]);
		for(i=b+1;i<=BN;i++)ans-=query(i,a[x]-1);
		for(i=(b-1)*BS+1;i<x;i++)if(a[i]>a[x]&&!use[i])ans--;
		for(i=min(b*BS,n);i>x;i--)if(a[i]<a[x]&&!use[i])ans--;
		change(b,a[x],-1);use[x]=1;
	}
}

BZOJ2821 卡了无数次常数，牺牲了ojkiller2，总算卡过去了。。。

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=100005,BS=250,BN=400;
int n,g,m,tot,ans,x,y,bx,by,i,j,w,top,st,ed,l,r,mid,tmp,first[N],last[N],now[N],a[N],v[N],c[N],q[N],d[403][403];
char ch;struct EG{int x,z;}eg[N];
bool cmp(EG a,EG b){return a.x<b.x||(a.x==b.x&&a.z<b.z);}
void read(int &x){
    for(ch=getchar();ch<'0';ch=getchar());
    for(x=0;ch>='0';ch=getchar())x=x*10+ch-'0';
}
int main(){
	read(n);read(g);read(m);
	for(i=1;i<=n;i++)read(a[i]),eg[i].x=a[i],eg[i].z=i;
	for(j=1;j<=BN;j++){
		memset(now,0,sizeof(now));tot=0;
		for(i=(j-1)*BS+1;i<=n;i++){
			if(!(now[a[i]]&1)&&now[a[i]])tot--;
			now[a[i]]++;if(!(now[a[i]]&1))tot++;
			d[j][(i-1)/BS+1]=tot;
		}
	}
	sort(eg+1,eg+n+1,cmp);
	for(i=1;i<=n;i++){
		if(!first[eg[i].x])first[eg[i].x]=i;
		last[eg[i].x]=i;
	}
	for(w=1;w<=m;w++){
		read(x);read(y);x=(x+ans)%n+1;y=(y+ans)%n+1;
		if(x>y)swap(x,y);bx=(x-1)/BS+1;by=(y-1)/BS+1;top=0;
		if(bx+1<=by-1){
			ans=d[bx+1][by-1];
			for(i=x;i<=bx*BS;i++)if(v[a[i]]!=w)v[a[i]]=w,c[a[i]]=1,q[++top]=a[i];else c[a[i]]++;
			for(i=(by-1)*BS+1;i<=y;i++)if(v[a[i]]!=w)v[a[i]]=w,c[a[i]]=1,q[++top]=a[i];else c[a[i]]++;
			for(i=1;i<=top;i++){
				st=bx*BS+1;ed=by*BS-BS;
				l=first[q[i]];r=last[q[i]]+1;
				while(l<r){
					mid=(l+r)>>1;
					if(st<=eg[mid].z)r=mid;else l=mid+1;
				}
				tmp=l;
				l=first[q[i]];r=last[q[i]]+1;
				while(l<r){
					mid=(l+r)>>1;
					if(ed<eg[mid].z)r=mid;else l=mid+1;
				}
				tmp=l-tmp;
				if(tmp==0&&c[q[i]]&&(c[q[i]]&1)==0)ans++;
				else if(tmp&&c[q[i]]&&(tmp&1)==0&&(c[q[i]]&1)==1)ans--;
				else if(tmp&&c[q[i]]&&(tmp&1)==1&&(c[q[i]]&1)==1)ans++;
			}
		}else for(ans=0,i=x;i<=y;i++)
				if(v[a[i]]!=w)v[a[i]]=w,c[a[i]]=1;else{
					c[a[i]]++;
					if(c[a[i]]&1)ans--;else ans++;
				}
		printf("%d\n",ans);
	}
}

BZOJ3744，d[i][j]表示第i块到第j块逆序对数，f[i][j]表示前i块比j大的数的个数，g[i][j]表示前i块比j小的数的个数，然后就可以在线求逆序对数了，时间复杂度O(n^1.5lgn)

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=50005,BS=250,BN=200;
int n,m,i,j,sum,now,ans,x,y,l,r,bx,by,b[N],c[N],a[N],v[N],d[203][203],f[203][N],g[203][N];
void add(int x){for(;x<=n;x+=x&-x)c[x]++;}
int query(int x){for(sum=0;x;x-=x&-x)sum+=c[x];return sum;}
int main(){
	scanf("%d",&n);
	for(i=1;i<=n;i++)scanf("%d",&a[i]),v[i]=a[i];
	sort(v+1,v+n+1);for(i=1;i<=n;i++)a[i]=lower_bound(v+1,v+n+1,a[i])-v;
	for(j=1;j<=BN;j++){
		memset(c,0,sizeof(c));now=0;
		for(i=(j-1)*BS+1;i<=n;i++){
			now+=query(n)-query(a[i]);
			add(a[i]);
			d[j][(i-1)/BS+1]=now;
		}
	}
	memcpy(b,a,sizeof(b));
	for(j=1;j<=BN;j++){
		l=(j-1)*BS+1;r=j*BS+1;
		sort(b+l,b+r);
		memcpy(f[j],f[j-1],sizeof(f[j]));
		memcpy(g[j],g[j-1],sizeof(g[j]));
		for(i=1;i<=n;i++){
			f[j][i]+=(b+r-upper_bound(b+l,b+r,i));
			g[j][i]+=(lower_bound(b+l,b+r,i)-b-l);
		}
	}
	scanf("%d",&m);
	while(m--){
		memset(c,0,sizeof(c));
		scanf("%d%d",&x,&y);x^=ans;y^=ans;ans=0;
		bx=(x-1)/BS+1;by=(y-1)/BS+1;
		if(bx+2<=by){
			ans=d[bx+1][by-1];
			for(i=y;i>(by-1)*BS;i--)ans+=query(a[i]-1)+f[by-1][a[i]]-f[bx][a[i]],add(a[i]);
			for(i=bx*BS;i>=x;i--)ans+=query(a[i]-1)+g[by-1][a[i]]-g[bx][a[i]],add(a[i]);
		}else for(i=y;i>=x;i--)ans+=query(a[i]-1),add(a[i]);
		printf("%d\n",ans);
	}
}

BZOJ4241 分块得到每一块答案，再维护一个前缀和，方便处理散的答案

#include<bits/stdc++.h>
#define N 100100
using namespace std;long long o,b[533][533];int n,m,i,j,w,x,y,X,Y,S=200,v[N],a[N],p[N],s[N],c[533][N];
int main(){
	for(scanf("%d%d",&n,&m),i=1;i<=n;i++)scanf("%d",&a[i]),v[i]=a[i],p[i]=(i-1)/S+1;
	for(sort(v+1,v+n+1),w=unique(v+1,v+n+1)-v,i=1;i<=n;i++)c[p[i]][a[i]=lower_bound(v+1,v+w,a[i])-v]++;
	for(i=1;i<=n;i+=S)for(o=0,memset(s,0,sizeof(s)),j=i;j<=n;j++)o=max(o,1ll*v[a[j]]*++s[a[j]]),b[p[i]][p[j]]=o;
	for(i=S+1;i<=n;i+=S)for(j=1;j<w;j++)c[p[i]][j]+=c[p[i]-1][j];
	for(;m--;printf("%lld\n",o)){
		scanf("%d%d",&x,&y);X=p[x];Y=p[y];o=b[X+1][Y-1];
		if(X==Y){
			for(i=x;i<=y;i++)s[a[i]]=0;
			for(i=x;i<=y;i++)o=max(o,1ll*v[a[i]]*++s[a[i]]);
		}else{
			for(i=x;i<=X*S;i++)s[a[i]]=c[Y-1][a[i]]-c[X][a[i]];
			for(i=Y*S-S+1;i<=y;i++)s[a[i]]=c[Y-1][a[i]]-c[X][a[i]];
			for(i=x;i<=X*S;i++)o=max(o,1ll*v[a[i]]*++s[a[i]]);
			for(i=Y*S-S+1;i<=y;i++)o=max(o,1ll*v[a[i]]*++s[a[i]]);
		}
	}
}

BZOJ4028 分块，如果两块的gcd不同了，就暴力重构/查找，相同则直接在set中找，时间复杂度O(n^1.5lgn)。

#include<bits/stdc++.h>
#define N 100100
using namespace std;set<int>p[1111];char s[9];long long z;int n,i,j,S=500,B,Q,x,y,v,A,a[N],bl[N],l[1111],r[1111],G[N],X[N];
void bt(int x){
	p[x].clear();G[l[x]]=a[l[x]];X[l[x]]=a[l[x]];p[x].insert(X[l[x]]);
	for(int i=l[x]+1;i<=r[x];i++)G[i]=__gcd(G[i-1],a[i]),p[x].insert(X[i]=X[i-1]^a[i]);
}
int main(){
	for(scanf("%d",&n),i=1;i<=n;i++)scanf("%d",&a[i]),bl[i]=(i-1)/S+1;
	for(B=(n-1)/S+1,i=1;i<=B;i++)l[i]=r[i-1]+1,r[i]=i*S,r[B]=n,bt(i);
	for(scanf("%d",&Q);Q--;)if(scanf("%s",s),s[0]=='M')scanf("%d%d",&x,&y),x++,a[x]=y,bt(bl[x]);else{
		for(scanf("%lld",&z),v=x=A=0,i=1;i<=B&&!A;v=__gcd(v,G[r[i]]),x^=X[r[i++]])if(__gcd(v,G[r[i]])!=v){for(j=l[i];j<=r[i]&&!A;j++)if(1ll*(X[j]^x)*__gcd(v,G[j])==z)A=j;}else if(z%v==0&&p[i].count((int)(z/v)^x))for(j=l[i];j<=r[i]&&!A;j++)if(1ll*(X[j]^x)*v==z)A=j;
		if(A)printf("%d\n",A-1);else puts("no");
	}
}

BZOJ1926 第一种数据按权值分块，时间复杂度O(r^2c+mc)。第二种数据使用莫队，并通过分块做到O(1)修改O(n^0.5)查询，时间复杂度O(mc^0.5)。

#include<bits/stdc++.h>
#define N 500500
using namespace std;struct P{int z,x,y;}p[40040];bool cmp(P a,P b){return a.z<b.z;}int R,C,S=1000,m,n,i,j,k,o,X1,Y1,X2,Y2,z,V,W,cnt,L,a[202][202],A[202][202][202],B[202][202][202],e[N],v[N],ans[20200],pos[N],c[N],sm[2222],ms[2222];
struct Q{int l,r,z,id;}q[20020];bool Cm(Q a,Q b){return pos[a.l]<pos[b.l]||pos[a.l]==pos[b.l]&&a.r<b.r;}
void add(int x,int z){c[x]+=z;sm[pos[x]]+=z*v[x];ms[pos[x]]+=z;}
void w1(){
	for(n=C,i=1;i<=n;i++)scanf("%d",&e[i]),v[i]=e[i],pos[i]=(i-1)/S;
	for(sort(v+1,v+n+1),cnt=unique(v+1,v+n+1)-v-1,i=1;i<=n;i++)e[i]=lower_bound(v+1,v+cnt+1,e[i])-v;
	for(i=1;i<=m;i++)scanf("%d%d%d%d%d",&V,&q[i].l,&V,&q[i].r,&q[i].z),q[i].id=i;
	for(sort(q+1,q+m+1,Cm),L=i=1,R=0;i<=m;i++){
		for(;R<q[i].r;)R++,add(e[R],1);for(;R>q[i].r;R--)add(e[R],-1);
		for(;L<q[i].l;L++)add(e[L],-1);for(;L>q[i].l;)L--,add(e[L],1);
		for(V=W=0,j=(n-1)/S;j>=0;j--)if(W+sm[j]>=q[i].z)break;else W+=sm[j],V+=ms[j];
		if(j>=0)for(k=(j+1)*S;k>=j*S+1&&W<q[i].z;k--)if(W+c[k]*v[k]>=q[i].z)V+=(q[i].z-W-1)/v[k]+1,W=q[i].z;else W+=c[k]*v[k],V+=c[k];
		if(W<q[i].z)ans[q[i].id]=0;else ans[q[i].id]=V;
	}
	for(i=1;i<=m;i++)if(ans[i])printf("%d\n",ans[i]);else puts("Poor QLW");
}
void w2(){
	for(i=1;i<=R;i++)for(j=1;j<=C;j++)scanf("%d",&a[i][j]),p[++n]=P{a[i][j],i,j};
	for(sort(p+1,p+n+1,cmp),k=1;k<=n;k++)A[(k-1)/C][p[k].x][p[k].y]=p[k].z,B[(k-1)/C][p[k].x][p[k].y]=1;
	for(k=0;k<R;k++)for(i=1;i<=R;i++)for(j=1;j<=C;j++)A[k][i][j]+=A[k][i-1][j]+A[k][i][j-1]-A[k][i-1][j-1],B[k][i][j]+=B[k][i-1][j]+B[k][i][j-1]-B[k][i-1][j-1];
	for(;m--;){
		for(scanf("%d%d%d%d%d",&X1,&Y1,&X2,&Y2,&z),W=0,k=R-1;k>=0;k--){
			o=A[k][X2][Y2]+A[k][X1-1][Y1-1]-A[k][X1-1][Y2]-A[k][X2][Y1-1];
			if(z<=o)break;z-=o;W+=B[k][X2][Y2]+B[k][X1-1][Y1-1]-B[k][X1-1][Y2]-B[k][X2][Y1-1];
		}
		if(k>=0)for(i=(k+1)*C;i>k*C&&z>0;i--)if(X1<=p[i].x&&p[i].x<=X2&&Y1<=p[i].y&&p[i].y<=Y2)z-=p[i].z,W++;
		if(V<z)puts("Poor QLW");else printf("%d\n",W);
	}
}
int main(){scanf("%d%d%d",&R,&C,&m);if(R==1)w1();else w2();}

BZOJ2128 分块，记录s[i][j][k]表示1~i,1~j，在块1~k的答案，每m分一块，总复杂度O(n^2m+qm)。

#include<bits/stdc++.h>
using namespace std;
int i,j,k,pa,pb,pc,n,m,O,Q,X1,Y1,X2,Y2,l,r,t,ans,v[255][255],s[255][255][255];long long a[3333],b[3333],c[3333];
int get(int i,int j,int O){return (a[i%pa+1]+b[i%pb+1]+c[i%pc+1]+a[j%pa+1]+b[j%pb+1]+c[j%pc+1])%O+1;}
struct P{int z,x,y;}p[66666];bool cmp(P a,P b){return a.z<b.z;}
int G(int z){
	int u,i,V=0,o;
	for(u=0;u<m;u++)if(p[u*n+1].z>z)break;
	if(p[u*n+1].z>z)u--;if(u==m)u--;
	if(u>=0){
		V=s[X2][Y2][u]+s[X1-1][Y1-1][u]-s[X2][Y1-1][u]-s[X1-1][Y2][u];o=u*n;
		for(i=2;i<=n;i++)if(p[o+i].z<=z&&p[o+i].z!=p[o+1].z)if(X1<=p[o+i].x&&p[o+i].x<=X2&&Y1<=p[o+i].y&&p[o+i].y<=Y2)V++;
	}return V;
}
int main(){
	for(scanf("%d",&pa),i=1;i<=pa;i++)scanf("%lld",&a[i]);
	for(scanf("%d",&pb),i=1;i<=pb;i++)scanf("%lld",&b[i]);
	for(scanf("%d",&pc),i=1;i<=pc;i++)scanf("%lld",&c[i]);
	for(scanf("%d%d%d%d",&n,&m,&O,&Q),i=1;i<=n;i++)for(j=1;j<=m;j++)v[i][j]=get(i,j,O),p[++t]=P{v[i][j],i,j};
	for(sort(p+1,p+t+1,cmp),i=1;i<=n;i++)for(j=1;j<=m;j++)for(k=0;k<m;k++)if(v[i][j]>p[k*n+1].z)s[i][j][k]=s[i-1][j][k]+s[i][j-1][k]-s[i-1][j-1][k];else s[i][j][k]=s[i][j-1][k]+s[i-1][j][k]-s[i-1][j-1][k]+1;
	for(i=1;i<=Q;i++){
		X1=get(i,1,n);Y1=get(i,2,m);X2=get(i,3,n);Y2=get(i,4,m);l=get(i,5,O);r=get(i,6,O);
		if(X1>X2)swap(X1,X2);if(Y1>Y2)swap(Y1,Y2);if(l>r)swap(l,r);ans^=(G(r)-G(l-1));
	}
	printf("%d",ans);
}

二、莫队算法

1.普通莫队

似乎就是[l,r]能影响到[l-1,r]和[l,r+1]时可以用，暴力分块先按左端点所在块排序，再按右端点排序

BZOJ2038：每次[l,r]改变只会影响到一个组合数，可以O(1)求出

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
const LL N=50005,BS=500;
LL n,m,i,l,r,k,ans,s[N],a[N],pos[N];
struct EG{LL a,b,l,r,z;}eg[N];
LL gcd(LL a,LL b){return b==0?a:gcd(b,a%b);}
LL sqr(LL x){return x*x;}
bool cmp(EG a,EG b){//按左端点所在块排序 
	if(pos[a.l]==pos[b.l])return a.r<b.r;
	return a.l<b.l;//所在块相同按右端点排序 
}
bool cmp2(EG a,EG b){return a.z<b.z;}
void update(int p,int add){//更新答案 
	ans-=sqr(s[a[p]]);
	s[a[p]]+=add;
	ans+=sqr(s[a[p]]);
}
int main(){
	scanf("%lld%lld",&n,&m);
	for(i=1;i<=n;i++)scanf("%lld",&a[i]),pos[i]=(i-1)/BS+1;
	for(i=1;i<=m;i++)scanf("%lld%lld",&eg[i].l,&eg[i].r),eg[i].z=i;
	sort(eg+1,eg+m+1,cmp);
	for(i=1,l=1,r=0;i<=m;i++){
		for(;r<eg[i].r;r++)update(r+1,1);//更新答案 
		for(;r>eg[i].r;r--)update(r,-1);
		for(;l<eg[i].l;l++)update(l,-1);
		for(;l>eg[i].l;l--)update(l-1,1);
		eg[i].a=ans-(eg[i].r-eg[i].l+1);//统计 
		eg[i].b=(eg[i].r-eg[i].l+1)*(eg[i].r-eg[i].l);
		k=gcd(eg[i].a,eg[i].b);
		eg[i].a/=k;eg[i].b/=k;
	}
	sort(eg+1,eg+m+1,cmp2);
	for(i=1;i<=m;i++)printf("%lld/%lld\n",eg[i].a,eg[i].b);
}

BZOJ3289莫队+树状数组，左右端点的左右移动可以用树状数组在logn的时间内维护出来

#include<cstdio>
#include<algorithm>
using namespace std;
const int N=50005,BS=500;
unsigned int now,sum,ans[N];
int i,l,r,n,m,a[N],v[N],pos[N],c[N];
struct EG{int l,r,z;}eg[N];
bool cmp(EG a,EG b){
	if(pos[a.l]==pos[b.l])return a.r<b.r;
	return a.l<b.l;
}
void add(int x,int key){for(;x<=n;x+=x&-x)c[x]+=key;}
unsigned int query(int x){for(sum=0;x;x-=x&-x)sum+=c[x];return sum;}
int main(){
	scanf("%d",&n);for(i=1;i<=n;i++)scanf("%d",&a[i]),v[i]=a[i],pos[i]=(i-1)/BS+1;
	sort(v+1,v+n+1);for(i=1;i<=n;i++)a[i]=lower_bound(v+1,v+n+1,a[i])-v;
	scanf("%d",&m);for(i=1;i<=m;i++)scanf("%d%d",&eg[i].l,&eg[i].r),eg[i].z=i;
	sort(eg+1,eg+m+1,cmp);
	for(i=1,l=1,r=0;i<=m;i++){
		for(;r<eg[i].r;)r++,add(a[r],1),now+=r-l+1-query(a[r]);
		for(;r>eg[i].r;r--)add(a[r],-1),now-=r-l-query(a[r]);
		for(;l<eg[i].l;l++)add(a[l],-1),now-=query(a[l]-1);
		for(;l>eg[i].l;)l--,add(a[l],1),now+=query(a[l]-1);
		ans[eg[i].z]=now;
	}
	for(i=1;i<=m;i++)printf("%d\n",ans[i]);
}

树上莫队和带修莫队待填。。似乎树上莫队就是按DFS序处理询问，带修莫队就是加一个时间维度像K-D树一样搞，时间复杂度O(n^(5/3))

2.树上莫队

树上莫队大概就是用括号序列表示一颗树，一对括号相互抵消，这样就像普通莫队一样搞就行了

SPOJ10707 标记每个点的DFS序，并记录其括号序列，对于每对询问，预处理LCA，如果它们是有父子关系的，那么区间为两个括号序列的左括号，否则要把左区间改为x的右括号，得到这些位置后，按括号序列分块，现在只要在排好序的询问上统计答案

我们要求的点是u-v的所有点，这也相当于root到u的所有点^root到v的所有点^(lca(u,v)if !=u&v)，这样和莫队一样让L和R一个一个走，当到达答案时判一下LCA就可以了，改变答案的时候做标记，如果走过那么标记为没走过，如果没走过标记为走过，并更新答案

#include<bits/stdc++.h>
#define N 44444
#define M 100100
using namespace std;
int n,m,i,x,y,t,tp,pt,tot,L,R,now,S=300,sum[N],to[M],pos[M],dfn[N],a[N],v[N],l[N],r[N],fir[N],ne[M],la[M],h[N],fa[N][18],ans[M];
struct Q{int l,r,id;}q[M];bool vis[N];
bool cmp(Q a,Q b){return pos[a.l]<pos[b.l]||pos[a.l]==pos[b.l]&&a.r<b.r;}
void ins(int x,int y){la[++tot]=y;ne[tot]=fir[x];fir[x]=tot;}
void dfs(int x){
	int i;dfn[x]=++tp;l[x]=++pt;to[pt]=x;
	for(i=1;i<=17;i++)fa[x][i]=fa[fa[x][i-1]][i-1];
	for(i=fir[x];i;i=ne[i])if(fa[x][0]!=la[i])fa[la[i]][0]=x,h[la[i]]=h[x]+1,dfs(la[i]);
	r[x]=++pt;to[pt]=x;
}
int lca(int x,int y){
    if(h[x]<h[y])swap(x,y);int t=h[x]-h[y],i;
    for(i=0;i<=17;i++)if(t>>i&1)x=fa[x][i];
    for(i=17;i>=0;i--)if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];
    return x==y?x:fa[x][0];
}
void go(int x){
	if(vis[x])now-=(--sum[a[x]]==0);else now+=(++sum[a[x]]==1);
	vis[x]^=1;
}
int main(){
	for(scanf("%d%d",&n,&m),i=1;i<=n;i++)scanf("%d",&a[i]),v[i]=a[i];
	for(sort(v+1,v+n+1),i=1;i<=n;i++)a[i]=lower_bound(v+1,v+n+1,a[i])-v;
	for(i=1;i<n;i++)scanf("%d%d",&x,&y),ins(x,y),ins(y,x);
	for(dfs(1),i=1;i<=pt;i++)pos[i]=(i-1)/S;
	for(i=1;i<=m;i++){
		scanf("%d%d",&x,&y);if(dfn[x]>dfn[y])swap(x,y);
		t=lca(x,y);if(t==x)q[i].l=l[x];else q[i].l=r[x];
		q[i].r=l[y];q[i].id=i;
	}
	for(sort(q+1,q+m+1,cmp),L=1,R=0,i=1;i<=m;i++){
		for(;L>q[i].l;go(to[--L]));
		for(;L<q[i].l;go(to[L++]));
		for(;R>q[i].r;go(to[R--]));
		for(;R<q[i].r;go(to[++R]));
		x=to[L];y=to[R];t=lca(x,y);
		if(x!=t&&y!=t)go(t);
		ans[q[i].id]=now;
		if(x!=t&&y!=t)go(t);
	}
	for(i=1;i<=m;i++)printf("%d\n",ans[i]);
}

据说这题还能在线做，好神啊~

3.树上带修莫队

树上带修莫队就是再增加一维时间，按照左端点所在块为第一关键字，右端点所在块为第二关键字，时间为第三关键字排序，块的大小为 N^2/3，这样如果每次改动的复杂度为O(1)，那么总的时间复杂度为N^5/3

WC2013糖果公园 按照树上带修莫队的方法统计出当前的答案就可以了

#include<bits/stdc++.h>
#define N 100100
using namespace std;
int n,m,k,i,x,y,t,L,R,l1,l2,tp,pt,T,tot,S=1333,las[N],c[N],v[N],w[N],h[N],s[N],l[N],r[N],dfn[N],pos[N<<1],to[N<<1],fir[N],ne[N<<1],la[N<<1],fa[N][18];
struct Q{int l,r,cur,id;}q[N];struct P{int x,pre,now;}p[N];bool vis[N];long long sum,ans[N];
bool cmp(Q a,Q b){return pos[a.l]<pos[b.l]||pos[a.l]==pos[b.l]&&pos[a.r]<pos[b.r]||pos[a.l]==pos[b.l]&&pos[a.r]==pos[b.r]&&a.cur<b.cur;}
void ins(int x,int y){la[++tot]=y;ne[tot]=fir[x];fir[x]=tot;}
void dfs(int x){
	int i;dfn[x]=++tp;l[x]=++pt;to[pt]=x;
	for(i=1;i<=17;i++)fa[x][i]=fa[fa[x][i-1]][i-1];
	for(i=fir[x];i;i=ne[i])if(fa[x][0]!=la[i])fa[la[i]][0]=x,h[la[i]]=h[x]+1,dfs(la[i]);
	r[x]=++pt;to[pt]=x;
}
int lca(int x,int y){
    if(h[x]<h[y])swap(x,y);int t=h[x]-h[y],i;
    for(i=0;i<=17;i++)if(t>>i&1)x=fa[x][i];
    for(i=17;i>=0;i--)if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];
    return x==y?x:fa[x][0];
}
void go(int x){
	if(vis[x])sum-=(long long)v[c[x]]*w[s[c[x]]--];else sum+=(long long)v[c[x]]*w[++s[c[x]]];
	vis[x]^=1;
}
void cg(int x,int y){if(vis[x])go(x),c[x]=y,go(x);else c[x]=y;}
int main(){
	for(scanf("%d%d%d",&n,&m,&k),i=1;i<=m;i++)scanf("%d",&v[i]);
	for(i=1;i<=n;i++)scanf("%d",&w[i]);
	for(i=1;i<n;i++)scanf("%d%d",&x,&y),ins(x,y),ins(y,x);
	for(i=1;i<=n;i++)scanf("%d",&c[i]),las[i]=c[i];
	for(dfs(1),i=1;i<=pt;i++)pos[i]=(i-1)/S;
	for(i=1;i<=k;i++)if(scanf("%d%d%d",&t,&x,&y),t){
		if(dfn[x]>dfn[y])swap(x,y);
		q[++l1].r=l[y];q[l1].id=l1;q[l1].cur=l2;
		t=lca(x,y);if(t==x)q[l1].l=l[x];else q[l1].l=r[x];
	}else p[++l2].x=x,p[l2].pre=las[x],p[l2].now=las[x]=y;
	for(sort(q+1,q+l1+1,cmp),L=1,R=0,T=i=1;i<=l1;i++){
		for(;T<=q[i].cur;T++)cg(p[T].x,p[T].now);for(;T>q[i].cur;T--)cg(p[T].x,p[T].pre);
		for(;L>q[i].l;go(to[--L]));for(;L<q[i].l;go(to[L++]));
		for(;R>q[i].r;go(to[R--]));for(;R<q[i].r;go(to[++R]));
		x=to[L];y=to[R];t=lca(x,y);
		if(x!=t&&y!=t)go(t);ans[q[i].id]=sum;if(x!=t&&y!=t)go(t);
	}
	for(i=1;i<=l1;i++)printf("%lld\n",ans[i]);
}

BZOJ4129 和上题差不多，修改做到O(1)可以用分块思想，记录一个块中出现数的个数，这样每个询问可以n^0.5查询，总时间复杂度O(n^1.67+n^1.5)

#include<bits/stdc++.h>
#define N 50050
using namespace std;
int n,m,k,i,j,x,y,t,o,L,R,l1,l2,tp,pt,T,tot,S=150,las[N],c[N],ans[N],h[N],s[N],l[N],r[N],dfn[N],sm[N],pos[N<<1],to[N<<1],fir[N],ne[N<<1],la[N<<1],fa[N][16];
struct Q{int l,r,cur,id;}q[N];struct P{int x,pre,now;}p[N];bool vis[N];
bool cmp(Q a,Q b){return pos[a.l]<pos[b.l]||pos[a.l]==pos[b.l]&&pos[a.r]<pos[b.r]||pos[a.l]==pos[b.l]&&pos[a.r]==pos[b.r]&&a.cur<b.cur;}
void ins(int x,int y){la[++tot]=y;ne[tot]=fir[x];fir[x]=tot;}
void dfs(int x){
	int i;dfn[x]=++tp;l[x]=++pt;to[pt]=x;
	for(i=1;i<=15;i++)fa[x][i]=fa[fa[x][i-1]][i-1];
	for(i=fir[x];i;i=ne[i])if(fa[x][0]!=la[i])fa[la[i]][0]=x,h[la[i]]=h[x]+1,dfs(la[i]);
	r[x]=++pt;to[pt]=x;
}
int lca(int x,int y){
    if(h[x]<h[y])swap(x,y);int t=h[x]-h[y],i;
    for(i=0;i<=15;i++)if(t>>i&1)x=fa[x][i];
    for(i=15;i>=0;i--)if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];
    return x==y?x:fa[x][0];
}
void go(int x){
	if(vis[x]){if(c[x]<=n)if(!--s[c[x]])sm[pos[c[x]]]--;}else if(c[x]<=n)if(!s[c[x]]++)sm[pos[c[x]]]++;
	vis[x]^=1;
}
void cg(int x,int y){if(vis[x])go(x),c[x]=y,go(x);else c[x]=y;}
int main(){
	for(scanf("%d%d",&n,&k),i=1;i<=n;i++)scanf("%d",&c[i]),las[i]=c[i];
	for(i=1;i<n;i++)scanf("%d%d",&x,&y),ins(x,y),ins(y,x);
	for(dfs(1),i=1;i<=100000;i++)pos[i]=i/S;
	for(i=1;i<=k;i++)if(scanf("%d%d%d",&t,&x,&y),t){
		if(dfn[x]>dfn[y])swap(x,y);
		q[++l1].r=l[y];q[l1].id=l1;q[l1].cur=l2;
		t=lca(x,y);if(t==x)q[l1].l=l[x];else q[l1].l=r[x];
	}else p[++l2].x=x,p[l2].pre=las[x],p[l2].now=las[x]=y;
	for(sort(q+1,q+l1+1,cmp),L=1,R=0,T=i=1;i<=l1;i++){
		for(;T<=q[i].cur;T++)cg(p[T].x,p[T].now);for(;T>q[i].cur;T--)cg(p[T].x,p[T].pre);
		for(;L>q[i].l;go(to[--L]));for(;L<q[i].l;go(to[L++]));
		for(;R>q[i].r;go(to[R--]));for(;R<q[i].r;go(to[++R]));
		x=to[L];y=to[R];t=lca(x,y);if(x!=t&&y!=t)go(t);
		for(o=0;sm[o]==S;o++);
		for(j=S*o;j<S*(o+1);j++)if(!s[j]){ans[q[i].id]=j;break;}
		if(x!=t&&y!=t)go(t);
	}
	for(i=1;i<=l1;i++)printf("%d\n",ans[i]);
}

三、块状链表

块状链表有三个基本操作

①find(p,b)找到位置p在链表的位置b

②splite(b,p)将第b块分裂成两块，前一块大小为p

③maintain(b)将b块之后的碎片合并

然后写代码就可以了。。

NOI2003 Editor ：抄了一下模板，但本地一直A不了，然后纠结了好久，结果放到BZOJ上就A了。。

#include<cstdio>
#include<cstring>
#define N 2100000
#define SZ 20000//一个线性表的最大大小
#define M 333//链表的个数
int T,n,p,i,cur,pos,list[M],next[SZ],sz[SZ];
char data[M][SZ],str[N],ch[99];
int min(int x,int y){return x<y?x:y;}
int newnode(){return list[pos++];}
void delnode(int t){list[--pos]=t;}
void find(int &p,int &b){//找到位置p在链表的位置b
	for(b=0;b!=-1&&p>sz[b];b=next[b])p-=sz[b];
}
void fillblock(int b,int n,char str[],int e){//更新b的信息 
	if(b==-1)return;
	next[b]=e;sz[b]=n;
	memcpy(data[b],str,n);
}
void splite(int b,int p){//将第b块分裂成两块，前一块大小为p
	if(b==-1||p==sz[b])return;
	int t=newnode();
	fillblock(t,sz[b]-p,data[b]+p,next[b]);
	next[b]=t;sz[b]=p;
}
void maintain(int b){//将b块之后的碎片合并
	for(;b!=-1;b=next[b])
		for(int t=next[b];t!=-1&&sz[b]+sz[t]<=SZ;t=next[b]){
			memcpy(data[b]+sz[b],data[t],sz[t]);
			sz[b]+=sz[t];next[b]=next[t];
			delnode(t);
		}
}
void insert(int p,int n,char *str){//插入 
	int b,t,i;
	find(p,b);
	splite(b,p);
	for(i=0;i+SZ<=n;i+=SZ){
		t=newnode();
		fillblock(t,SZ,str+i,next[b]);
		next[b]=t;b=t;
	}
	if(n-i){
		t=newnode();
		fillblock(t,n-i,str+i,next[b]);
		next[b]=t;
	}
	maintain(b);
}
void erase(int p,int n){//删除 
	int b,t,i;
	find(p,b);
	splite(b,p);
	for(i=next[b];i!=-1&&n>sz[i];i=next[i])n-=sz[i];
	splite(i,n);i=next[i];
	for(t=next[b];t!=i;t=next[b]){
		next[b]=next[t];
		delnode(t);
	}
    maintain(b); 
}
void get(int p,int n,char *str){//输出 
	int b,t,i;
	find(p,b);
	i=min(n,sz[b]-p);
	memcpy(str,data[b]+p,i);
	for(t=next[b];t!=-1&&i+sz[t]<=n;i+=sz[t],t=next[t])
		memcpy(str+i,data[t],sz[t]);
	if(n-i&&t!=-1)memcpy(str+i,data[t],n-i);
	str[n]='\0';
}
int main(){
	for(i=1;i<M;i++)list[i]=i;
	pos=1;next[0]=-1;sz[0]=0;
	scanf("%d",&T);
	while(T--){
		scanf("%s",ch);
		if(ch[0]=='I'){
			scanf("%d",&n);
			for(i=0;i<n;i++){
				char c=getchar();
				str[i]=c;
				if(c=='\n')--i;  
			}
			insert(cur,n,str);
		}else if(ch[0]=='D')scanf("%d",&n),erase(cur,n);
		else if(ch[0]=='G')scanf("%d",&n),get(cur,n,str),printf("%s\n",str);
		else if(ch[0]=='M')scanf("%d",&cur);
		else if(ch[0]=='P')cur--;
		else if(ch[0]=='N')cur++;
	}
}

NOI2005维修数列

#include<cstdio>
#include<cstring>
#include<iostream>
const int oo=2e9,BS=700,MN=5e5+10,MB=MN/BS*2+1000;
using namespace std;
int data[MB][BS],sz[MB],sav[MB],totsum[MB],sidemax[MB][2],maxsum[MB],flist[MB],next[MB],pos;
bool same[MB],rev[MB];
int newnode(){return flist[++pos];}
void delnode(int t){flist[pos--]=t;}
void find(int &p,int &b){for(b=0;p>sz[b];b=next[b])p-=sz[b];}//找到所在的块 
void maintainblock(int b){//重新制作块 
	if(same[b]){//有相同标记 
		totsum[b]=sav[b]*sz[b];
		if(sav[b]>0)maxsum[b]=totsum[b];else maxsum[b]=sav[b];
		sidemax[b][0]=sidemax[b][1]=maxsum[b];
	}else{//没有相同标记 
		totsum[b]=0;maxsum[b]=-oo;
		for(int last=0,i=sz[b]-1;i>=0;--i){//中间最大的一段 
			totsum[b]+=data[b][i];last+=data[b][i];
			if(maxsum[b]<last)maxsum[b]=last;
			if(last<0)last=0;
		}
		sidemax[b][0]=-oo;
		for(int last=0,i=0;i<sz[b];++i){//左边起最大的一段 
			last+=data[b][i];
			if(sidemax[b][0]<last)sidemax[b][0]=last;
		}
		sidemax[b][1]=-oo;
		for(int last=0,i=sz[b]-1;i>=0;--i){//右边起最大的一段 
			last+=data[b][i];
			if(sidemax[b][1]<last)sidemax[b][1]=last;
		}
	}
}
void rever(int b){//翻转 
	if(b==-1||!rev[b])return;rev[b]=0;if(same[b])return;
	for(int l=0,r=sz[b]-1;l<r;++l,--r)swap(data[b][l],data[b][r]);
	swap(sidemax[b][0],sidemax[b][1]);
}
void maintainlist(int b){//将b以后的碎块合并 
	for(bool x=0;b!=-1;b=next[b],x=0){
		for(int t=next[b];t!=-1&&sz[b]+sz[t]<=BS;t=next[b],x=true){
			if(!(same[b]&&same[t]&&sav[b]==sav[t])){
				rever(b);rever(t);
				if(same[b])for(int i=0;i<sz[b];++i)data[b][i]=sav[b];
				for(int i=0;i<sz[t];++i)data[b][sz[b]+i]=same[t]?sav[t]:data[t][i];
				same[b]=0;
			}
			sz[b]+=sz[t];next[b]=next[t];delnode(t);
		}
		if(x)maintainblock(b);
	}
}
void fillblock(int b,int sv,int n,int e){//维护一个值相同块的信息 
	same[b]=true;sav[b]=sv;next[b]=e;
	sz[b]=n;rev[b]=0;maintainblock(b);
}
void fillblock(int b,int str[],int n,int e){//维护一个块的信息 
	same[b]=rev[b]=0;sz[b]=n;next[b]=e;
	memcpy(data[b],str,n*sizeof(int));maintainblock(b);
}
void splite(int b,int p){//将块b从p处断开 
	if(b==-1||sz[b]==p)return;
	int t=newnode();rever(b);
	if(same[b])fillblock(t,sav[b],sz[b]-p,next[b]);else fillblock(t,data[b]+p,sz[b]-p,next[b]);
	next[b]=t;sz[b]=p;maintainblock(b);
}
void insert(int p,int n,int str[]){//插入 
	int b,i,t;find(p,b);splite(b,p);
	for(i=0;i+BS<=n;i+=BS){
		t=newnode();fillblock(t,str+i,BS,next[b]);
		next[b]=t;b=t;
	}
	if(n-i){fillblock(t=newnode(),str+i,n-i,next[b]);next[b]=t;}
	maintainlist(next[b]);
}
void erase(int p,int n){//删除 
	int b,e;find(p,b);splite(b,p);
	for(e=next[b];n>sz[e];e=next[e])n-=sz[e];
	splite(e,n);e=next[e];
	for(int t=next[b];t!=e;t=next[b])next[b]=next[t],delnode(t);
}
int list[MB];
void reverse(int p,int n){//翻转 
	int b,e,i,t;find(p,b);splite(b,p);
	for(e=next[b];n>sz[e];e=next[e])n-=sz[e];
	splite(e,n);e=next[e];
	for(i=0,t=next[b];t!=e;t=next[t],++i)list[i]=t;
	next[b]=list[--i];
	for(;i>=0;--i){
		next[list[i]]=i?list[i-1]:t;
		rev[list[i]]=!rev[list[i]];
	}
	maintainlist(b);
}
void makesame(int p,int n,int v){//相同值 
	int b,t;find(p,b);splite(b,p);
	for(t=next[b];n>sz[t];n-=sz[t],t=next[t])fillblock(t,v,sz[t],next[t]);
	if(n)splite(t,n),fillblock(t,v,n,next[t]);
	maintainlist(b);
}
int getsum_in_block(int b,int p,int n){//块中总和 
	int sum,l,r;if(same[b])return sav[b]*n;
	if(rev[b]){l=sz[b]-p-n;r=sz[b]-p-1;}else{l=p;r=p+n-1;}
	for(sum=0;l<=r;++l)sum+=data[b][l];
	return sum;
}
void getsum(int p,int n){//总和 
	int b,t,sum,i;find(p,b);
	sum=getsum_in_block(b,p,min(n,sz[b]-p));n-=min(n,sz[b]-p);
	for(t=next[b]; n>sz[t]; t=next[t])sum+=totsum[t],n-=sz[t];
	sum+=getsum_in_block(t,0,n);
	printf("%d\n",sum);
}
void getmaxsum(){//最大区间和 
	int res=-oo,last=0;
	for(int b=0; b!=-1; b=next[b]){
		res=max(max(res,last+sidemax[b][rev[b]]),maxsum[b]);
		last=max(max(last+totsum[b],sidemax[b][!rev[b]]),0);
	}
	printf("%d\n",res);
}
int main(){
	int n,T,i,p,v,a[MN];char order[99];
	for(int i=1;i<MB;++i)flist[i]=i;next[0]=-1;
	scanf("%d%d",&n,&T);for(i=0;i<n;++i)scanf("%d",a+i);
	insert(0,n,a);
	while(T--){
		scanf("%s",order);
		if(order[2]=='X')getmaxsum();
		else switch(order[0]){
		case 'I':scanf("%d%d",&p,&n);for(i=0;i<n;++i)scanf("%d",a+i);insert(p,n,a);break;
		case 'D':scanf("%d%d",&p,&n);erase(p-1, n);break;
		case 'M':scanf("%d%d%d",&p,&n,&v);makesame(p-1, n ,v);break;
		case 'R':scanf("%d%d",&p,&n);reverse(p-1,n);break;
		case 'G':scanf("%d%d",&p,&n);getsum(p-1,n);break;
		}
	}
}

四、块状树

就是把树分块，每块大小为n^0.5，建块状树时只要当前块不大于n^0.5就把子节点加入，然后维护每个块的信息就行了

ZJOI2008树的统计 比树剖和LCT都短哦

#include<cstdio>
#include<cmath>
#include<algorithm>
#define inf 1e9
#define N 30003
using namespace std;char s[9];
int T,n,i,x,y,BS,tot,tot2,ans,mx,a[N],fa[N],high[N],own[N],mav[N],sum[N],fir[N],fir2[N],la[N<<1],ne[N<<1],la2[N<<1],ne2[N<<1];
void ins(int x,int y){la[++tot]=y;ne[tot]=fir[x];fir[x]=tot;}
void ins2(int x,int y){la2[++tot2]=y;ne2[tot2]=fir2[x];fir2[x]=tot2;}
void build(int x){//建立块状树 
	for(int i=fir[x];i;i=ne[i]){
		int y=la[i];
		if(fa[x]!=y){//如果没有到根号n就把子节点加入 
			if(sum[own[x]]<BS)ins2(x,y),sum[own[y]=own[x]]++;
			high[y]=high[x]+1;fa[y]=x;
			build(y);
		}
	}
}
void dfs(int x,int sm,int ma){//对每个块进行DFS 
	sum[x]=sm+=a[x];mav[x]=ma=max(ma,a[x]);
	for(int i=fir2[x];i;i=ne2[i])dfs(la2[i],sm,ma);
}
void change(int x,int y){a[x]=y;own[x]==x?dfs(x,0,-inf):dfs(x,sum[fa[x]],mav[fa[x]]);}//改变块内答案 
void Q(int x,int y){//统计 
	for(ans=0,mx=-inf;x!=y;){
		if(high[x]<high[y])swap(x,y);//改深度大的 
		if(own[x]==own[y])ans+=a[x],mx=max(mx,a[x]),x=fa[x];else{
			if(high[own[x]]<high[own[y]])swap(x,y);
			ans+=sum[x];mx=max(mx,mav[x]);x=fa[own[x]];
		}
	}
	ans+=a[x];mx=max(mx,a[x]);
}
int main(){
	scanf("%d",&n);BS=ceil(sqrt(n));
	for(i=1;i<n;i++)scanf("%d%d",&x,&y),ins(x,y),ins(y,x);
	for(i=1;i<=n;i++)scanf("%d",&a[i]),own[i]=i,sum[i]=1;
	build(1);scanf("%d",&T);
	for(i=1;i<=n;i++)if(own[i]==i)dfs(i,0,-inf);
	while(T--){
		scanf("%s%d%d",s,&x,&y);
		if(s[0]=='C')change(x,y);else{
			Q(x,y);
			if(s[1]=='S')printf("%d\n",ans);else printf("%d\n",mx);
		}
	}
}

BZOJ3720：块状树的一些操作，对每个块进行排序，加点的时候如果块大于BS就重开一个块，BS=(nlgn)^0.5时效果最好

#include<cstdio>
#include<algorithm>
#include<cmath>
#define N 60010
using namespace std;
int n,i,top,T,p,x,y,BS,ans,a[N],own[N],fa[N];
struct BL{//块的信息 
	int num[700],size;
	int ask(int k){return size-(upper_bound(num+1,num+size+1,k)-num-1);}
}blk[6000];
struct BG{//存图 
	int fir[N],tot,la[N<<1],ne[N<<1];
	void add(int x,int y){la[++tot]=y;ne[tot]=fir[x];fir[x]=tot;}
}g1,g3;
void build(int x){//建立块状树 
	int t=own[x];blk[t].num[++blk[t].size]=a[x];
	for(int i=g1.fir[x];i;i=g1.ne[i]){
		int y=g1.la[i];
		if(fa[x]!=y){//如果没有到BS就把子节点加入  
			if(blk[t].size<BS)own[y]=t;else own[y]=++top;
			fa[y]=x;
			if(t!=own[y])g3.add(t,own[y]);
			build(y);
		}
	}
}
int QB(int x,int k){//处理整块 
	int ans=blk[x].ask(k);
	for(int i=g3.fir[x];i;i=g3.ne[i])ans+=QB(g3.la[i],k);
	return ans;
}
int Q(int x,int k){//处理散点 
	int ans=a[x]>k;
	for(int i=g1.fir[x];i;i=g1.ne[i]){
		int y=g1.la[i];
		if(fa[x]!=y)if(own[x]==own[y])ans+=Q(y,k);else ans+=QB(own[y],k);
	}
	return ans;
}
int main(){
	scanf("%d",&n);BS=sqrt(n*log(n)/log(2));
	for(i=1;i<n;i++)scanf("%d%d",&x,&y),g1.add(x,y),g1.add(y,x);
	for(i=1;i<=n;i++)scanf("%d",&a[i]);
	own[1]=++top;build(1);scanf("%d",&T);
	for(i=1;i<=top;i++)sort(blk[i].num+1,blk[i].num+blk[i].size+1);
	while(T--){
		scanf("%d%d%d",&p,&x,&y);x^=ans;y^=ans;
		if(p==0)printf("%d\n",ans=Q(x,y));//询问x的子数中比y大的个数 
		else if(p==1){//修改单点权值 
			int t=own[x];
			for(int i=1;i<=blk[t].size;i++)
				if(blk[t].num[i]==a[x]){blk[t].num[i]=a[x]=y;break;}
			sort(blk[t].num+1,blk[t].num+blk[t].size+1);
		}else{//加点 
			int t=own[x];
			g1.add(x,++n);a[n]=y;fa[n]=x;
			if(blk[t].size<BS){//加到块中 
				blk[t].num[++blk[t].size]=y;
				sort(blk[t].num+1,blk[t].num+blk[t].size+1);
				own[n]=t;
			}else{//新建一个块 
				g3.add(t,++top);
				blk[top].num[++blk[top].size]=y;
				own[n]=top;
			}
		}
	}
}

待做：BZOJ3337、3731

• 相关文章推荐
• 全局相关文章