奇怪的码长增加了

魔板

bool Type(int x) {return x==son[fa[x]][1];}
void Update(int x) {size[x]=cnt[x]+size[son[x][0]]+size[son[x][1]];}
void change(int x) {
	int y=fa[x],z=fa[y],k=Type(x);
	fa[x]=z;
	if(z) son[z][Type(y)]=x; else fa[x]=0;
	son[y][k]=son[x][k^1];
	fa[son[y][k]]=y;
	son[x][k^1]=y;
	fa[y]=x;
	Update(y),Update(x);
}
void splay(int x) {
	for(int f=fa[x];f=fa[x];change(x)) {
		if(fa[f]) change(Type(x)==Type(f)?f:x);
	}
	root=x;
}
void init(int val) {
	tot++;
	data[tot]=val,fa[tot]=0,size[tot]=cnt[tot]=1,root=tot;
}

void Insert(int val) {
	if(!tot) {init(val);return;}
	tot++;
	int p=root; bool flag=0;
	while(p) {
		size[p]++;
		if(val==data[p]) {
			flag=1;cnt[p]++;tot--; break;
		}
		else if(val<data[p]) {
			if(son[p][0]) p=son[p][0];
			else {son[p][0]=tot;break;}
		}
		else {
			if(son[p][1]) p=son[p][1];
			else {son[p][1]=tot;break;}
		}
	}
	if(!flag) {
		fa[tot]=p;data[tot]=val,cnt[tot]=size[tot]=1;
		splay(tot);
//		printf("!%d %d %d\n",tot,cnt[tot],size[tot]);
	}
	else splay(p);
}
int fd_kth(int k) {
	int p=root;
	while(p) {
//		printf("(%d)%d %d\n",data[p],data[son[p][1]],k);
		if(size[son[p][1]]+1<=k&&size[son[p][1]]+cnt[p]>=k) break;
		if(size[son[p][1]]+1>k) {p=son[p][1];}
		else {k-=size[son[p][1]]+cnt[p];p=son[p][0];}
	}
	return data[p];
}
int Find(int val) {
	int p=root;
	while(p) {
		if(data[p]==val) return p;
		if(data[p]<val) p=son[p][1];
		else p=son[p][0];
	}
	return 0;
}

当然，很多时候跟区间相关的题目会用到一种操作，如\([L,R]\)，\(x=fd(L-1),y=fd(R+1)\),\(splay(x,0),splay(y,x)\)然后我们把区间\([L,R]\)卡成了\(son[y][0]\)的子树，然后操作就对该子树即可

区间翻转问题

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
bool Lazy[N];
int a[N],fa[N],root,son[N][2],val[N],sum[N],mx[N],size[N],tot;
void P_up(int u) {	//xxxx
	int ls=son[u][0],rs=son[u][1];
	sum[u]=val[u]+sum[ls]+sum[rs];
	mx[u]=max(val[u],max(mx[ls],mx[rs]));
	size[u]=1+size[ls]+size[rs];
}
void P_dw(int u) {
	if(!Lazy[u])return;
	swap(son[u][0],son[u][1]);
	Lazy[son[u][0]]^=1,Lazy[son[u][1]]^=1;
	Lazy[u]=0;
}
int Build(int l,int r) {		//????????
	if(l>r)return 0;
	int mid=(l+r)>>1;
	int u=++tot;
	size[u]=1,val[u]=sum[u]=mx[u]=a[mid];
	son[u][0]=Build(l,mid-1),son[u][1]=Build(mid+1,r);
	fa[son[u][0]]=u,fa[son[u][1]]=u;
	P_up(u);
	return u;
}
bool Type(int x) {return x==son[fa[x]][1];}
void change(int x) {
	int y=fa[x],z=fa[y],k=Type(x);
	fa[x]=z;
	if(z) son[z][Type(y)]=x; else root=x;
	son[y][k]=son[x][k^1];
	fa[son[y][k]]=y;
	son[x][k^1]=y;
	fa[y]=x;
	P_up(y),P_up(x);
}
void splay(int x,int y) {
	for(int f=fa[x];f=fa[x],f!=y;change(x)) {
		if(fa[f]!=y) change(Type(x)==Type(f)?f:x);
	}
	if(!y) root=x;
}
int fd_kth(int k) {
	int p=root;
	while(p) {
		P_dw(p);
		int ls=son[p][0];
		if(size[ls]+1==k) break;
		else if(size[ls]+1<k) {k-=size[ls]+1;p=son[p][1];}
		else p=son[p][0];
	}
	return p;
}
int Query(int l,int r,int opt) {
	int x=fd_kth(l-1),y=fd_kth(r+1);
	splay(x,0),splay(y,x);
	int k=son[y][0];
	if(!opt) return sum[k];
	else return mx[k];
}
void Update(int l,int r) {
	int x=fd_kth(l-1),y=fd_kth(r+1);
	splay(x,0),splay(y,x);
	int k=son[y][0];
	Lazy[k]^=1;
}
int main() {
	int n,m;
	scanf("%d%d",&n,&m);
	a[1]=a[n+2]=0;
	for(int i=1;i<=n;i++) {scanf("%d",&a[i+1]);}
	Build(1,n+2); root=1;
	for(int i=1;i<=m;i++) {
		int opt,k,d,l,r;
		scanf("%d",&opt);
		if(opt==1) {
			scanf("%d",&k);
			int p=fd_kth(k+1);
			splay(p,0);
			printf("%d\n",val[p]);
		}
		else if(opt==2) {
			scanf("%d%d",&k,&d);
			int p=fd_kth(k+1);
			val[p]+=d;
			splay(p,0);
		}
		else {
			scanf("%d%d",&l,&r); 
			l++;r++;
			if(opt==5) Update(l,r);
			else printf("%d\n",Query(l,r,opt-3));
		}
//		printf("?%d %d %d\n",root,son[root][0],son[root][1]);
	}
	return 0;
}