UVA11996 Jewel Magic

た入场券 2021-12-23 14:01 175阅读 0赞

### 思路 ###

splay维护序列的hash值即可  
因为有rev操作，还要维护反串的hash值

### 代码 ###

#include <cstdio> #include <cstring> #include <algorithm> using namespace std; unsigned long long my_pow[600000]; const int base=131; struct Node{ unsigned long long hashx,hashx_rev; int son[2],inv,sz,val,fa; }SPT[600000]; int Nodecnt,root,a[600000],len,n,m; void get_my_pow(void){ my_pow[0]=1; for(int i=1;i<=500000;i++) my_pow[i]=my_pow[i-1]*base; } void init(void){ Nodecnt=root=len=0; memset(SPT,0,sizeof(SPT)); memset(a,0,sizeof(a)); } void pushup(int o){ SPT[o].sz=SPT[SPT[o].son[0]].sz+SPT[SPT[o].son[1]].sz+1; SPT[o].hashx=SPT[SPT[o].son[0]].hashx*my_pow[SPT[SPT[o].son[1]].sz+1]+SPT[o].val*my_pow[SPT[SPT[o].son[1]].sz]+SPT[SPT[o].son[1]].hashx; SPT[o].hashx_rev=SPT[SPT[o].son[1]].hashx_rev*my_pow[SPT[SPT[o].son[0]].sz+1]+SPT[o].val*my_pow[SPT[SPT[o].son[0]].sz]+SPT[SPT[o].son[0]].hashx_rev; } void pushdown(int o){ if(o&&SPT[o].inv){ if(SPT[o].son[0]){ swap(SPT[SPT[o].son[0]].son[0],SPT[SPT[o].son[0]].son[1]); SPT[SPT[o].son[0]].inv^=1; swap(SPT[SPT[o].son[0]].hashx,SPT[SPT[o].son[0]].hashx_rev); } if(SPT[o].son[1]){ swap(SPT[SPT[o].son[1]].son[0],SPT[SPT[o].son[1]].son[1]); SPT[SPT[o].son[1]].inv^=1; swap(SPT[SPT[o].son[1]].hashx,SPT[SPT[o].son[1]].hashx_rev); } SPT[o].inv^=1; } } int find(int val,int o){ if(!o) return 0; pushdown(o); if(val==SPT[SPT[o].son[0]].sz+1) return o; else if(val<=SPT[SPT[o].son[0]].sz) return find(val,SPT[o].son[0]); else return find(val-SPT[SPT[o].son[0]].sz-1,SPT[o].son[1]); } int new_node(int val,int fa){ int o=++Nodecnt; SPT[o].hashx=SPT[o].hashx_rev=SPT[o].val=val; SPT[o].inv=0; SPT[o].sz=1; SPT[o].fa=fa; SPT[o].son[0]=SPT[o].son[1]=0; return o; } int build(int l,int r,int f){ if(l>r) return 0; int mid=(l+r)>>1; int o=new_node(a[mid],f); SPT[o].son[0]=build(l,mid-1,o); SPT[o].son[1]=build(mid+1,r,o); pushup(o); return o; } int isrl(int o){ return SPT[SPT[o].fa].son[1]==o; } void rorate(int o){ int f=SPT[o].fa; int g=SPT[f].fa; pushdown(f); pushdown(o); int which=isrl(o); if(g) SPT[g].son[SPT[g].son[1]==f]=o; SPT[o].fa=g; SPT[f].son[which]=SPT[o].son[which^1]; SPT[SPT[o].son[which^1]].fa=f; SPT[o].son[which^1]=f; SPT[f].fa=o; pushup(f); pushup(o); } void splay(int o,int goal){ for(int f;(f=SPT[o].fa)!=goal;rorate(o)) if(SPT[f].fa!=goal) rorate(isrl(f)==isrl(o)?f:o); if(!goal) root=o; } void debug(int o){ if(!o) return; pushdown(o); debug(SPT[o].son[0]); if(SPT[o].val>=0&&SPT[o].val<=1) printf("%d",SPT[o].val); else printf(" %d ",SPT[o].val); debug(SPT[o].son[1]); } void insert(int p,int c){ len++; int t=new_node(c,0); int lx=p,rx=p+1; int lxx=find(lx+1,root),rxx=find(rx+1,root); splay(lxx,0); splay(rxx,lxx); pushdown(root); pushdown(SPT[root].son[1]); SPT[SPT[root].son[1]].son[0]=t; SPT[t].fa=SPT[root].son[1]; pushup(SPT[root].son[1]); pushup(root); } void del(int p){ len--; int lx=p-1,rx=p+1; int lxx=find(lx+1,root),rxx=find(rx+1,root); splay(lxx,0); splay(rxx,lxx); pushdown(root); pushdown(SPT[root].son[1]); SPT[SPT[root].son[1]].son[0]=0; pushup(SPT[root].son[1]); pushup(root); } void rev(int l,int r){ int lx=l-1,rx=r+1; int lxx=find(lx+1,root),rxx=find(rx+1,root); splay(lxx,0); splay(rxx,lxx); pushdown(root); pushdown(SPT[root].son[1]); int o=SPT[SPT[root].son[1]].son[0]; SPT[o].inv^=1; swap(SPT[o].son[0],SPT[o].son[1]); swap(SPT[o].hashx,SPT[o].hashx_rev); } bool check(int p1,int p2,int x){ if(x==0) return true; unsigned long long hash1,hash2; { int lx=p1-1,rx=p1+x; int lxx=find(lx+1,root),rxx=find(rx+1,root); splay(lxx,0); splay(rxx,lxx); pushdown(root); pushdown(SPT[root].son[1]); hash1=SPT[SPT[SPT[root].son[1]].son[0]].hashx; } { int lx=p2-1,rx=p2+x; int lxx=find(lx+1,root),rxx=find(rx+1,root); splay(lxx,0); splay(rxx,lxx); pushdown(root); pushdown(SPT[root].son[1]); hash2=SPT[SPT[SPT[root].son[1]].son[0]].hashx; } return hash1==hash2; } int lcp(int p1,int p2){ int l=0,r=min(len-p1+1,len-p2+1),ans=0; while(l<=r){ int mid=(l+r)>>1; if(check(p1,p2,mid)) ans=mid,l=mid+1; else r=mid-1; } return ans; } int main(){ get_my_pow(); while(scanf("%d %d",&n,&m)==2){ init(); len=n; for(int i=2;i<=n+1;i++){ char c=getchar(); while(c!='0'&&c!='1') c=getchar(); a[i]=c-'0'; } a[1]=-0x3f3f3f3f; a[n+2]=0x3f3f3f3f; root=build(1,n+2,0); for(int i=1;i<=m;i++){ int opt,p1,p2,c; scanf("%d",&opt); if(opt==1){ scanf("%d %d",&p1,&c); insert(p1,c); } else if(opt==2){ scanf("%d",&p1); del(p1); } else if(opt==3){ scanf("%d %d",&p1,&p2); rev(p1,p2); } else{ scanf("%d %d",&p1,&p2); printf("%d\n",lcp(p1,p2)); } } } return 0; }

转载于:https://www.cnblogs.com/dreagonm/p/10715306.html