monkey cheng

不卡常，但是很难写。

只有排序操作就是一个颜色段均摊，加上区间异或操作颜色段要维护“排序后

\oplus\ x

”的信息，还需支持分裂合并，采取 01-trie 维护。类似于线段树分裂合并，时空复杂度均为

O(n\log n)

。

具体来说，外层维护一颗线段树，线段树的叶子连向以这个点为左端点的颜色段的 01-trie。分裂

[l,r]

到

[l,x)

时直接把 01-trie 分裂，再把叶子节点的标记复制到

x

上。合并先各自下传叶子标记然后 01-trie 合并。这是因为分裂时的顺序应该是上次排序时的顺序，下传叶子节点标记就会变成异或之后的顺序。区间异或就直接打 tag。

使用压缩 01-trie，即只维护分叉点，空间可以达到

O(n)

。合并时，需要根据最长公共前缀来新增节点；分裂时可以直接复制点和边，处理完之后检查这个点能不能被删除，这样不会使空间复杂度增大。

CPP

#include<bits/stdc++.h>
using namespace std;
bool mst;
const int maxn=1e5+5,LIM=28,M=300000;
int n,q,a[maxn],xds[maxn<<2],add[maxn<<2],cnt[maxn<<2],leaf[maxn],C;
namespace Trie{
	struct node{int ch,len,lv;node(){ch=len=lv=0;}};
	vector<int> bin;
	node t[2][M];
	int sze[M],val[M],add[M],rt[maxn],tot=0;
	node operator +(node A,node B){node C;C.ch=A.ch+B.ch,C.len=A.len+B.len,C.lv=A.lv+B.lv;return C;}
	void clear(int p){sze[p]=0,val[p]=0,add[p]=0,t[0][p]=t[1][p]=node();}
	int qsy(){
		if(bin.size()){int u=bin.back();bin.pop_back();clear(u);return u;}
		return ++tot;
	}
	void pushup(int k){
		sze[k]=sze[t[0][k].ch]+sze[t[1][k].ch];
		val[k]=val[t[0][k].ch]^val[t[1][k].ch];
	}
	inline int getv(int v,int l,int r){return (v>>l)&((1<<r-l+1)-1);}
	void ADD(int k,int d,int v){
		if(!k||!v)return ;
		if(d>=0&&(v&(1<<d)))swap(t[0][k],t[1][k]);
		if(t[0][k].ch)t[0][k].lv^=getv(v,d-t[0][k].len+1,d);
		if(t[1][k].ch)t[1][k].lv^=getv(v,d-t[1][k].len+1,d);
		add[k]^=v;val[k]^=((sze[k]&1)*v);
	}
	void pushdown(int k,int d){
		if(!add[k]||!k||d<0)return ;
		ADD(t[0][k].ch,d-t[0][k].len,add[k]);
		ADD(t[1][k].ch,d-t[1][k].len,add[k]);
		add[k]=0;
	}
	int cntch(int k){return (t[1][k].ch!=0)+(t[0][k].ch!=0);}
	void check(int u,int k,int v,int d){
		if(cntch(v)!=1)return ;
		pushdown(u,d);pushdown(v,d-t[k][u].len);
		int ch=t[0][v].ch+t[1][v].ch,len=t[0][v].len+t[1][v].len,lv=t[0][v].lv+t[1][v].lv;
		t[k][u].ch=ch,t[k][u].lv=(t[k][u].lv<<len)+lv,t[k][u].len=len+t[k][u].len;
		clear(v);bin.push_back(v);
	}
	void check(int u,int d){for(int i:{0,1})if(t[i][u].ch)check(u,i,t[i][u].ch,d);}
	void split(int &x,int &y,int k,int d,int cur=0){
		if(!k)return swap(x,y);
		if(sze[x]==k)return ;
		y=qsy();
		if(d==-1){
			int a=k,b=sze[x]-k;
			val[x]=(a&1)*cur,val[y]=(b&1)*cur;
			sze[x]=a,sze[y]=b;
			return ;
		}
		pushdown(x,d),pushdown(y,d);
		if(sze[t[0][x].ch]>=k){
			t[1][y]=t[1][x];t[1][x]=node();
			if(sze[t[0][x].ch]!=k)t[0][y].len=t[0][x].len,t[0][y].lv=t[0][x].lv; 
			split(t[0][x].ch,t[0][y].ch,k,d-t[0][x].len,cur^(t[0][x].lv<<(d-t[0][x].len+1)));
		}else{
			t[1][y].len=t[1][x].len,t[1][y].lv=t[1][x].lv; 
			split(t[1][x].ch,t[1][y].ch,k-sze[t[0][x].ch],d-t[1][x].len,cur^(t[1][x].lv<<(d-t[1][x].len+1)));
		}
		check(x,d),check(y,d);
		pushup(x),pushup(y);
	}
	void INS(int u,int k,int v,int d){
		int x=qsy();node tmp;
		tmp.ch=x,tmp.lv=(t[k][u].lv>>(t[k][u].len-d)),tmp.len=d;int k2=(t[k][u].lv>>(t[k][u].len-d-1))&1;
		t[k2][x].ch=v,t[k2][x].lv=(t[k][u].lv&((1<<t[k][u].len-d)-1)),t[k2][x].len=t[k][u].len-d;
		t[k][u]=tmp;
		pushup(x);
	}
	void SINS(int u,int v,int k){
		int x=t[k][u].lv^t[k][v].lv;
		if(x==0)return ;
		int L=t[k][u].len-__lg(x)-1;
		INS(u,k,t[k][u].ch,L),INS(v,k,t[k][v].ch,L);
	}
	int merge(int x,int &y,int d){
		if(d<0){
			val[x]^=val[y];
			sze[x]+=sze[y];
			clear(y),bin.push_back(y);y=0;
			return x;
		}
		pushdown(x,d),pushdown(y,d);
		for(auto i:{0,1}){
			if(t[i][x].ch&&t[i][y].ch){
				if(t[i][x].len>t[i][y].len)INS(x,i,t[i][x].ch,t[i][y].len);
				else if(t[i][x].len<t[i][y].len)INS(y,i,t[i][y].ch,t[i][x].len);
				SINS(x,y,i);
			}
		}
		for(int i:{0,1}){
			if(!t[i][x].ch||!t[i][y].ch)t[i][x]=t[i][x]+t[i][y];
			else t[i][x].ch=merge(t[i][x].ch,t[i][y].ch,d-t[i][x].len);
		}
		clear(y),bin.push_back(y);y=0;
		pushup(x);check(x,d);
		return x;
	}
	void build(){
		for(int i=1;i<=n;i++){
			rt[i]=qsy();int k=(a[i]>>LIM)&1;
			t[k][rt[i]].len=LIM+1,t[k][rt[i]].lv=a[i],t[k][rt[i]].ch=qsy();
			sze[t[k][rt[i]].ch]=sze[rt[i]]=1,val[t[k][rt[i]].ch]=val[rt[i]]=a[i];
		}
	}
}
#define ls (k<<1)
#define rs (k<<1|1)
#define mid ((l+r)>>1)
void ADD(int k,int v){xds[k]^=((cnt[k]&1)*v),add[k]^=v;}
void pushup(int k,int l,int r){
	if(l<r)xds[k]=xds[ls]^xds[rs],cnt[k]=cnt[ls]+cnt[rs];
	else cnt[k]=Trie::sze[Trie::rt[l]],xds[k]=Trie::val[Trie::rt[l]]^(add[k]*(cnt[k]&1));
}
void Pushdown(int k,int l){if(Trie::rt[l])Trie::ADD(Trie::rt[l],LIM,add[k]);add[k]=0;}
void pushdown(int k,int l,int r){if(l<r)ADD(ls,add[k]),ADD(rs,add[k]),add[k]=0;}
set<pair<int,int> > st;
int query(int k,int l,int r,int x,int y){
	if(x<=l&&r<=y)return xds[k];
	pushdown(k,l,r);
	int res=0;
	if(x<=mid)res^=query(ls,l,mid,x,y);
	if(mid<y)res^=query(rs,mid+1,r,x,y);
	return res;
}
void Push(int k,int l,int r,int x){
	if(l==r)return pushup(k,l,r);
	pushdown(k,l,r);
	if(x<=mid)Push(ls,l,mid,x);
	else Push(rs,mid+1,r,x);
	pushup(k,l,r);
}
void PPush(int k,int l,int r,int x){
	if(l==r)return Pushdown(k,l),pushup(k,l,r);
	pushdown(k,l,r);
	if(x<=mid)PPush(ls,l,mid,x);
	else PPush(rs,mid+1,r,x);
	pushup(k,l,r);
}
void Push(int x){Push(1,1,n,x);}
void PPush(int x){PPush(1,1,n,x);}
void SPLIT(int x){
	auto it=st.upper_bound((pair<int,int>){x,n+1});--it;
	int l=(*it).first,r=(*it).second;
	if(x==l)return ;
	PPush(x),Push(l);
	Trie::split(Trie::rt[l],Trie::rt[x],x-l,LIM);
	Push(l);pushup(leaf[l],l,l);ADD(leaf[x],add[leaf[l]]);Push(x);
	st.erase({l,r});st.insert({l,x-1});st.insert({x,r}); 
}
void modify(int k,int l,int r,int x,int y,int v){
	if(x<=l&&r<=y)return ADD(k,v);
	pushdown(k,l,r);
	if(x<=mid)modify(ls,l,mid,x,y,v);
	if(mid<y)modify(rs,mid+1,r,x,y,v);
	pushup(k,l,r);
}
void build(int k,int l,int r){
	if(l==r)return leaf[l]=k,pushup(k,l,r);
	build(ls,l,mid);build(rs,mid+1,r);
	pushup(k,l,r);
}
void MERGE(int x,int y){
	PPush(x),PPush(y);
	Trie::rt[x]=Trie::merge(Trie::rt[x],Trie::rt[y],LIM);
	Push(x);Push(y);
}
void SORT(int l,int r){
	SPLIT(l);if(r+1<=n)SPLIT(r+1);
	auto it=st.upper_bound((pair<int,int>){l,0});
	vector<pair<int,int>> V;
	while((*it).first<=r)V.push_back(*it),++it;
	for(auto u:V)PPush(u.first);
	for(int i=1;i<V.size();i++)MERGE(V[0].first,V[i].first);
	for(auto x:V)st.erase(x);
	st.insert({l,r});
}
void pd(int k,int l,int r){
	pushup(k,l,r);
	if(l==r)return ;
	pd(ls,l,mid),pd(rs,mid+1,r);
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>n>>q;
	for(int i=0;i<=n+1;i++)st.insert({i,i});
	for(int i=1;i<=n;i++)cin>>a[i];
	Trie::build();build(1,1,n);
	for(int i=1;i<=q;i++){
		int tp,l,r,v;C=i;
		cin>>tp>>l>>r;
		if(tp==1){
			cin>>v;
			SPLIT(l);if(r+1<=n)SPLIT(r+1);
			modify(1,1,n,l,r,v);
		}else if(tp==2)SORT(l,r);
		else{
			SPLIT(l);if(r+1<=n)SPLIT(r+1);
			cout<<query(1,1,n,l,r)<<endl;
		}
	}
	return 0;
}

文章操作

相关推荐

评论

monkey cheng