链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1014
题意：动态修改字符串，动态查询某两个后缀之间的$LCP$长度。
这题肯定一堆人刚开始：$woc$这题好水啊，后缀数据结构放肆撸啊……
等看到后半段：$woc$这个修改怎么改啊……
实际上这个东西跟后缀数据结构半毛钱关系没有……正确做法就是$Hash$……不停地插入字符，修改整棵子树的$Hash$值，然后就是动态的修改$Hash$值……转啊转……修改……转……然后就出来了……
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cstring> 5 #define ls(x) ((x)->ch[0]) 6 #define rs(x) ((x)->ch[1]) 7 #define fa(x) (x->pa) 8 using namespace std; 9 const int base=2333,maxn=100005; 10 unsigned long long tim[maxn];char s[maxn]; 11 struct node 12 { 13 int size,num;unsigned long long Has; 14 node *ch[2],*pa; 15 node(int has); 16 int islc(){return ls(pa)==this;} 17 void maintain(); 18 }*null=new node(0),*root=null; 19 node::node(int has) 20 { 21 ch[0]=ch[1]=pa=null; 22 num=Has=has;size=has?1:0; 23 } 24 void node::maintain() 25 { 26 size=ch[0]->size+ch[1]->size+1; 27 Has=ch[0]->Has*tim[ch[1]->size+1]+num*tim[ch[1]->size]+ch[1]->Has; 28 } 29 void Rotate(node* rt,int d) 30 { 31 node *t=rt->ch[d^1]; 32 if(rt->pa!=null)rt->pa->ch[rt->islc()^1]=t;else root=t; 33 t->pa=rt->pa; 34 rt->ch[d^1]=t->ch[d]; 35 if(t->ch[d]!=null)t->ch[d]->pa=rt; 36 t->ch[d]=rt,rt->pa=t; 37 rt->maintain();t->maintain(); 38 } 39 void Splay(node* x,node *tar) 40 { 41 for(node *rt=x->pa;rt!=tar;rt=x->pa) 42 { 43 if(rt->pa==tar){Rotate(rt,x->islc());break;} 44 if(x->islc()==rt->islc())Rotate(rt->pa,x->islc()); 45 else Rotate(rt,x->islc()); 46 Rotate(x->pa,x->islc()); 47 } 48 x->maintain(); 49 } 50 void find(node *rt,int val,node *tar) 51 { 52 for(;;) 53 { 54 if(val<=ls(rt)->size)rt=ls(rt); 55 else 56 { 57 val-=ls(rt)->size; 58 if(val==1)break; 59 val--,rt=rs(rt); 60 } 61 } 62 Splay(rt,tar); 63 } 64 void build(node* &x,int l,int r) 65 { 66 if(l>r)return ; 67 int mid=(l+r)>>1;x=new node(s[mid]-'a'+1); 68 build(x->ch[0],l,mid-1),build(x->ch[1],mid+1,r); 69 x->ch[0]->pa=x,x->ch[1]->pa=x;x->maintain(); 70 } 71 void init() 72 { 73 tim[0]=1; 74 for(int i=1;i<=100001;i++)tim[i]=tim[i-1]*base; 75 scanf("%s",s);root=new node(20010117),root->ch[1]=new node(20010117); 76 build(root->ch[1]->ch[0],0,strlen(s)-1); 77 root->ch[1]->ch[0]->pa=root->ch[1],root->ch[1]->pa=root;root->ch[1]->maintain(),root->maintain(); 78 } 79 bool check(int x,int y,int val) 80 { 81 find(root,x,null);find(root,x+val+1,root); 82 unsigned long long Has1=root->ch[1]->ch[0]->Has; 83 find(root,y,null);find(root,y+val+1,root); 84 unsigned long long Has2=root->ch[1]->ch[0]->Has; 85 return Has1==Has2; 86 } 87 int Query(int x,int y) 88 { 89 int l=0,r=root->size-1-max(x,y),mid; 90 while(l<=r) 91 { 92 mid=(l+r)>>1; 93 if(check(x,y,mid))l=mid+1; 94 else r=mid-1; 95 } 96 return r; 97 } 98 int haha() 99 { 100 init();char s[5]; 101 int m;scanf("%d",&m); 102 while(m--) 103 { 104 scanf("%s",s);int x,y; 105 switch(s[0]) 106 { 107 case 'R':scanf("%d%s",&x,s); 108 find(root,x+1,null); 109 root->num=s[0]-'a'+1;root->maintain();break; 110 case 'I':scanf("%d%s",&x,s); 111 find(root,x+1,null);find(root,x+2,root); 112 root->ch[1]->ch[0]=new node(s[0]-'a'+1),root->ch[1]->ch[0]->pa=root->ch[1];root->ch[1]->maintain();root->maintain();break; 113 default:scanf("%d%d",&x,&y);printf("%d ",Query(x,y)); 114 } 115 } 116 } 117 int sb=haha(); 118 int main(){;}