题目

用的 AVL 树，分裂是双 log 的，其他操作均是单 log。目前 MLE+TLE+RE ，34分。求调或者复杂度证伪

#include<bits/stdc++.h>
#define N 200005
#define ll long long
using namespace std;
int q,rt[N];
ll lstans;
struct operate{
	#define BF(u) (h[ch[u][0]]-h[ch[u][1]])
	#define ls(u) (ch[u][0])
	#define rs(u) (ch[u][1])
	int tot,ch[N*90][2],siz[N*90],val[N*90],h[N*90],tag[N*90];
	ll sum[N*90];
	int newnode(int x){
		int u=++tot;
		val[u]=sum[u]=x,siz[u]=h[u]=1,ls(u)=rs(u)=tag[u]=0;
		return u;
	}
	int copy(int x){
		if(!x)	return 0;
		int u=++tot;
		val[u]=val[x],sum[u]=sum[x],siz[u]=siz[x];
		h[u]=h[x],ls(u)=ls(x),rs(u)=rs(x),tag[u]=tag[x];
		return u;
	}
	void pushup(int u){
		siz[u]=siz[ls(u)]+siz[rs(u)]+1;
		h[u]=max(h[ls(u)],h[rs(u)])+1;
		sum[u]=sum[ls(u)]+sum[rs(u)]+val[u];
	}
	void pushdown(int u){
		if(!tag[u])	return;
		swap(ls(u),rs(u));
		ls(u)=copy(ls(u));
		rs(u)=copy(rs(u));
		if(ls(u))	tag[ls(u)]^=tag[u];
		if(rs(u))	tag[rs(u)]^=tag[u];
		tag[u]=0;
	}
	void rotate(int &u,bool f){
		int v=copy(ch[u][f]);
		pushdown(v);
		ch[u][f]=ch[v][!f];
		ch[v][!f]=u;
		pushup(u),pushup(v),u=v;
	}
	void maintain(int &u){
		pushdown(u);
		int chk=BF(u);
		if(chk>1){
			pushdown(ls(u)=copy(ls(u)));
			if(BF(ls(u))<=0)	rotate(ls(u),1);
			rotate(u,0);
		}
		else if(chk<-1){
			pushdown(rs(u)=copy(rs(u)));
			if(BF(rs(u))>=0)	rotate(rs(u),0);
			rotate(u,1);
		}
		else if(u)	pushup(u);
	}
	int merge(int u,int v){
		if(!u||!v)	return u+v;
		int tmp=h[u]-h[v];
		if(abs(tmp)<=1){
			u=copy(u),v=copy(v);
			pushdown(u),pushdown(v);
			if(tmp>=0){
				int w=kth(u,siz[u]),nrt;
				del(u,siz[u]),nrt=newnode(w);
				ls(nrt)=u,rs(nrt)=v,maintain(nrt);
				return nrt;
			}
			else{
				int w=kth(v,1),nrt;
				del(v,1),nrt=newnode(w);
				ls(nrt)=u,rs(nrt)=v,maintain(nrt);
				return nrt;
			}
		}
		if(h[u]>h[v]){
			u=copy(u),pushdown(u);
			rs(u)=merge(rs(u),v);
			maintain(u);
			return u;
		}
		else{
			v=copy(v),pushdown(v);
			ls(v)=merge(u,ls(v));
			maintain(v);
			return v;
		}
	}
	void split(int &rt1,int &rt2,int u,int k){
		pushdown(u);
		int x=ls(u),y=rs(u),z=newnode(val[u]);
		if(x){
			if(siz[x]<=k)	rt1=merge(rt1,x);
			else	split(rt1,rt2,x,k);
		}
		if(1+siz[x]<=k)	rt1=merge(rt1,z);
		else	rt2=merge(rt2,z); 
		if(y){
			if(k<=siz[x]+1)	rt2=merge(rt2,y);
			else	split(rt1,rt2,y,k-siz[x]-1);
		}
	}
	void insert(int &u,int k,int w){
		if(!u)	return void(u=newnode(w));
		pushdown(u);
		if(k<=siz[ls(u)]){
			ls(u)=copy(ls(u));
			insert(ls(u),k,w);
		}
		else{
			rs(u)=copy(rs(u));
			insert(rs(u),k-siz[ls(u)]-1,w);
		}
		maintain(u);
	}
	void del(int &u,int k){
		pushdown(u);
		if(k==siz[ls(u)]+1){
			int v=u;
			if(ls(u)&&(v=rs(u))){
				while(ls(v))	v=ls(v);
				val[u]=val[v],rs(u)=copy(rs(u));
				del(rs(u),1);
			}
			else	u=ls(u)?ls(u):rs(u);
		}
		else if(k<=siz[ls(u)]){
			ls(u)=copy(ls(u));
			del(ls(u),k);
		}
		else{
			rs(u)=copy(rs(u));
			del(rs(u),k-siz[ls(u)]-1);
		}
		maintain(u);
	}
	int kth(int u,int x){
		int tmp=0;
		while(u){
			pushdown(u);
			if((tmp=siz[ls(u)]+1)==x)	return val[u];
			else	u=((tmp>x)?ls(u):(x-=tmp,rs(u)));
		}
		return -1;
	}
	void change(int &u,int l,int r){
		int x=0,y=0,z=0,t=0;
		if(r!=siz[u])	split(t,z,u,r);
		else	t=u;
		if(l!=1)	split(x,y,t,l-1);
		else	y=t;
		y=copy(y),tag[y]^=1;
		u=merge(merge(x,y),z);
	}
	ll query(int u,int k){
		pushdown(u);
		int res=0;
		if(k<siz[ls(u)])	return query(ls(u),k);
		if(k==siz[ls(u)])	return sum[ls(u)];
		if(k==siz[ls(u)]+1)	return sum[ls(u)]+val[u];
		if(k>siz[ls(u)]+1)	return query(rs(u),k-siz[ls(u)]-1)+sum[ls(u)]+val[u];
	}
	void print(int x){
		if(!x)	return;
		cout<<x<<' '<<val[x]<<' '<<val[ls(x)]<<' '<<val[rs(x)]<<' '<<siz[x]<<' '<<sum[x]<<' '<<tag[x]<<'\n';
		print(ls(x)),print(rs(x));
	}
}T;
signed main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>q;
	for(int i=1;i<=q;i++){
		int op,id;
		ll y,x;
		cin>>id>>op,rt[i]=T.copy(rt[id]);
		switch(op){
			case 1:{
				cin>>x>>y;
				x^=lstans;
				y^=lstans;
				T.insert(rt[i],x,y);
				break;
			}
			case 2:{
				cin>>x,x^=lstans;
				T.del(rt[i],x);
				break;
			}
			case 3:{
				cin>>x>>y;
				x^=lstans;
				y^=lstans;
				T.change(rt[i],x,y);
				break;
			}
			case 4:{
				cin>>x>>y;
				x^=lstans;
				y^=lstans;
				cout<<(lstans=T.query(rt[i],y)-T.query(rt[i],x-1))<<'\n';
				break;
			}
		}
	}
	return 0;
}