BZOJ3217 : ALOEXT

희생양 트리 세트 Trie, Trie 합병은 라인 트리로 합병합니다. 상수 최적화에 주의하십시오.
 
AC800 문제 기념~
 

#include<cstdio>

#include<cmath>

#include<algorithm>

using namespace std;

const int N=200010,inf=19,M=32000010;

struct info{

  int v1,v2;

  info(){v1=v2=0;}

  info(int _v1,int _v2){v1=_v1,v2=_v2;}

}maxv;

inline info merge(info a,info b){

  if(b.v1>a.v1){

    a.v2=b.v2>a.v1?b.v2:a.v1;

    a.v1=b.v1;

  }else if(b.v1>a.v2)a.v2=b.v1;

  return a;

}

struct node{int l,r,v;node(){}node(int _l,int _r,int _v){l=_l,r=_r,v=_v;}}T[M];

int rub,getn[M];

const double A=0.8;

int size[N],real[N],ex[N],son[N][2],val[N],f[N],tot,root,id[N],cnt;

info mv[N];

int h[N],pool[N];

int ans,cntpool,cntone,one[N];

int n,q,x,y,i,Pow[20],Inv[20];char ch;

//Trie begin

inline void Max(int&a,int b){if(a<b)a=b;}

inline int Newtrienode(int l,int r,int v){

  int x=getn[rub--];

  T[x]=node(l,r,v);

  return x;

}

void Ins(int&x,int a,int c,int p){

  if(!x)x=Newtrienode(0,0,0);

  T[x].v+=p;

  if(~a)Ins(c&Pow[a]?T[x].r:T[x].l,a-1,c,p);

}

int Merge(int x,int y){

  if(!x&&!y)return 0;

  return Newtrienode(Merge(T[x].l,T[y].l),Merge(T[x].r,T[y].r),T[x].v+T[y].v);

}

inline int Ask(int x,int c){

  int t=1048575,a;

  for(a=inf;t>ans&&~a;a--)if(c&Pow[a]){

    if(T[T[x].l].v)x=T[x].l;else t&=Inv[a],x=T[x].r;

  }else{

    if(T[T[x].r].v)x=T[x].r;else t&=Inv[a],x=T[x].l;

  }

  return t;

}

inline void Ask(int c){

  int i;

  for(i=1;i<=cntone;i++)Max(ans,one[i]^c);

  for(i=1;i<=cntpool;i++)Max(ans,Ask(pool[i],c));

}

void deltree(int x){

  if(!x)return;

  deltree(T[x].l);deltree(T[x].r);

  getn[++rub]=x;

}

//Trie end

//Scapegoat begin

inline void up(int x){

  mv[x]=info(ex[x]?val[x]:0,0);

  if(son[x][0])mv[x]=merge(mv[x],mv[son[x][0]]);

  if(son[x][1])mv[x]=merge(mv[x],mv[son[x][1]]);

}

inline int newnode(int p,int fa){

  int x=++tot;

  f[x]=fa;size[x]=real[x]=ex[x]=1;son[x][0]=son[x][1]=0;

  val[x]=p;

  mv[x]=info(p,0);

  Ins(h[x]=0,inf,p,1);

  return x;

}

inline int Newnode(int x,int fa){

  f[x]=fa;size[x]=1;real[x]=ex[x];son[x][0]=son[x][1]=0;

  mv[x]=info(ex[x]?val[x]:0,0);

  h[x]=0;

  return x;

}

int ins(int x,int p,int b){

  size[x]++;real[x]++;mv[x]=merge(mv[x],info(p,0));

  Ins(h[x],inf,p,1);

  if(!son[x][b])return son[x][b]=newnode(p,x);else return ins(son[x][b],p,b);

}

void dfs(int x){

  if(son[x][0])dfs(son[x][0]);

  id[++cnt]=x;

  if(son[x][1])dfs(son[x][1]);

}

int build(int fa,int l,int r){

  int mid=(l+r)>>1,x=Newnode(id[mid],fa);

  if(l<mid)size[x]+=size[son[x][0]=build(x,l,mid-1)],real[x]+=real[son[x][0]];

  if(r>mid)size[x]+=size[son[x][1]=build(x,mid+1,r)],real[x]+=real[son[x][1]];

  h[x]=Merge(h[son[x][0]],h[son[x][1]]);

  if(ex[x])Ins(h[x],inf,val[x],1);

  up(x);

  return x;

}

inline int rebuild(int x){

  cnt=0;dfs(x);

  for(int i=1;i<=cnt;i++)deltree(h[id[i]]);

  return build(f[x],1,cnt);

}

inline int kth(int k,int p){

  int x=root,rank;

  while(1){

    size[x]++;real[x]++;mv[x]=merge(mv[x],info(p,0));Ins(h[x],inf,p,1);

    rank=real[son[x][0]]+1;

    if(k==rank&&ex[x])return x;

    if(k<rank)x=son[x][0];else k-=rank+ex[x]-1,x=son[x][1];

  }

}

inline void kthchange(int k,int p){

  int x=root,rank,del;

  while(1){

    rank=real[son[x][0]]+1;

    if(k==rank&&ex[x])break;

    if(k<rank)x=son[x][0];else k-=rank+ex[x]-1,x=son[x][1];

  }

  for(del=val[x],val[x]=p;x;x=f[x])Ins(h[x],inf,del,-1),Ins(h[x],inf,p,1),up(x);

}

inline void kthdel(int k){

  int x=root,rank,del;

  while(1){

    rank=real[son[x][0]]+1;

    if(k==rank&&ex[x])break;

    if(k<rank)x=son[x][0];else k-=rank+ex[x]-1,x=son[x][1];

  }

  for(del=val[x],ex[x]=0;x;x=f[x])real[x]--,Ins(h[x],inf,del,-1),up(x);

}

inline void kthins(int k,int p){

  if(!root){root=newnode(p,0);return;}

  int x;

  if(k==1)x=ins(root,p,0);

  else if(k>n)x=ins(root,p,1);

  else{

    x=kth(k,p);

    if(son[x][0])x=ins(son[x][0],p,1);else{

      son[x][0]=newnode(p,x);

      x=son[x][0];

    }

  }

  int z=x,deep=0;while(f[z])z=f[z],deep++;

  if(deep<log(tot)/log(1/A))return;

  while((double)size[son[x][0]]<A*size[x]&&(double)size[son[x][1]]<A*size[x])x=f[x];

  if(!x)return;

  if(x==root){root=rebuild(x);return;}

  int y=f[x],b=son[y][1]==x,now=rebuild(x);

  son[y][b]=now;

}

inline void ask(int x,int a,int b,int c,int d){

  if(!x)return;

  if(c<=a&&b<=d){maxv=merge(maxv,mv[x]);if(h[x])pool[++cntpool]=h[x];return;}

  int mid=a+real[son[x][0]];

  if(ex[x]&&c<=mid&&mid<=d)maxv=merge(maxv,info(val[x],0)),one[++cntone]=val[x];

  if(c<mid)ask(son[x][0],a,mid-1,c,d);

  if(d>=mid+ex[x])ask(son[x][1],mid+ex[x],b,c,d);

}

//Scapegoat end

inline void read(int&a){

  char ch;while(!(((ch=getchar())>='0')&&(ch<='9')));

  a=ch-'0';while(((ch=getchar())>='0')&&(ch<='9'))(a*=10)+=ch-'0';

}

int main(){

  for(Pow[0]=i=1;i<=inf;i++)Pow[i]=Pow[i-1]<<1;

  for(i=0;i<=inf;i++)Inv[i]=Pow[i]^1048575;

  for(i=1;i<M;i++)getn[++rub]=i;

  read(n);read(q);

  for(i=1;i<=n;i++)read(val[i]),id[i]=i,ex[i]=1;

  root=build(0,1,tot=n);

  while(q--){

    while(!(((ch=getchar())=='D')||(ch=='F')||(ch=='C')||(ch=='I')));

    read(x);

    if(ch!='D')read(y);

    if(ch=='F'){

      x=(x+ans)%n,y=(y+ans)%n;

      maxv=info();cntpool=cntone=0;

      ask(root,1,n,x+1,y+1);

      ans=0;

      Ask(maxv.v2);

      printf("%d
",ans);

    }else if(ch=='C')x=(x+ans)%n,y=(y+ans)&1048575,kthchange(x+1,y);

    else if(ch=='I')x=(x+ans)%n,y=(y+ans)&1048575,kthins(x+1,y),n++;

    else x=(x+ans)%n,kthdel(x+1),n--;

  }

  return 0;

}