支持插入修改什么的序列操作显然是Splay啊。
每个结点维护一下子树hash值即可。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 |
// <1014.cpp> - 05/19/16 17:36:52 // This file is created by XuYike's black technology automatically. // Copyright (C) 2015 ChangJun High School, Inc. // I don't know what this program is. #include <iostream> #include <vector> #include <algorithm> #include <cstring> #include <cstdio> #include <cmath> using namespace std; typedef long long lol; typedef unsigned long long ull; int gi(){ int res=0,fh=1;char ch=getchar(); while((ch>'9'||ch<'0')&&ch!='-')ch=getchar(); if(ch=='-')fh=-1,ch=getchar(); while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar(); return fh*res; } const int MAXN=100010; const int INF=1e9; const int seed=31; int n,root; char ch[MAXN]; ull h[MAXN],ha[MAXN]; int f[MAXN],s[MAXN][2]; int size[MAXN],val[MAXN]; inline void update(int x){ int l=s[x][0],r=s[x][1]; size[x]=size[l]+size[r]+1; ha[x]=ha[r]+val[x]*h[size[r]]+ha[l]*h[size[r]+1]; } void build(int l,int r,int last){ if(l>r)return; int m=(l+r)>>1; if(l==r)size[m]=1; else{ build(l,m-1,m); build(m+1,r,m); } f[m]=last;s[last][m>last]=m; update(m); } int src(int now,int k){ int l=s[now][0],r=s[now][1]; if(size[l]+1==k)return now; if(size[l]>=k)return src(l,k); return src(r,k-size[l]-1); } inline void R(int a,int &k){ int p=f[a],g=f[p]; bool l=a==s[p][1],r=!l; if(p==k)k=a; else s[g][s[g][1]==p]=a;f[a]=g; f[s[a][r]]=p;s[p][l]=s[a][r]; f[p]=a;s[a][r]=p; update(p);update(a); } inline void splay(int a,int &k){ while(a!=k){ int p=f[a]; if(p!=k){ if((s[p][0]==a)^(s[f[p]][0]==p))R(a,k); else R(p,k); } R(a,k); } } inline void split(int l,int r){ splay(src(root,l),root); splay(src(root,r+2),s[root][1]); } inline ull geth(int l,int r){split(l,r);return ha[s[s[root][1]][0]];} inline int ask(int x,int y){ int l=0,r=n-2-max(x,y); while(l<r){ int m=(l+r+1)>>1; if(geth(x,x+m)==geth(y,y+m))l=m; else r=m-1; } return l+(geth(x,x+l)==geth(y,y+l)); } inline void change(int x,char c){ splay(src(root,x+1),root); val[root]=c-'a'+1; update(root); } inline void insert(int x,char c){ val[++n]=c-'a'+1; split(x+1,x); s[s[root][1]][0]=n; f[n]=s[root][1]; update(n); update(f[n]); update(root); } int main(){ scanf("%s",ch+1); n=strlen(ch+1); h[0]=1; for(int i=1;i<MAXN;i++)h[i]=h[i-1]*seed; for(int i=1;i<=n;i++)val[i+1]=ch[i]-'a'+1; val[1]=val[n+2]=0; build(1,n+2,0); root=(n+3)>>1; n=n+2; int m=gi(); while(m--){ scanf("%s",ch); if(ch[0]=='Q')printf("%d\n",ask(gi(),gi())); else{ int x=gi();scanf("%s",ch+1); if(ch[0]=='R')change(x,ch[1]); else insert(x,ch[1]); } } return 0; } |