monkey cheng
Union_of_Britain · · 题解
不卡常，但是很难写。
只有排序操作就是一个颜色段均摊，加上区间异或操作颜色段要维护“排序后
具体来说，外层维护一颗线段树，线段树的叶子连向以这个点为左端点的颜色段的 01-trie。分裂
使用压缩 01-trie，即只维护分叉点，空间可以达到
#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;
}