[文章目录]
Description
维护带插入修改字符的字符串的任意两后缀的最长公共前缀。长度<=10^5
平衡树维护区间hash值。查询复杂度log^2的。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef unsigned long long ll;
int n,m;
ll bin[101000];
struct node
{
node *c[2],*fa;
char w; int siz; ll ha;
node(char x);
void pushup();
}*null=new node(0),*root;
node::node(char x)
{
c[0]=c[1]=fa=null ? null : this;
siz=null ? 1 : 0;
w=x; ha=x;
}
void node::pushup()
{
ha=c[0]->ha+w*bin[c[0]->siz]+c[1]->ha*bin[c[0]->siz+1];
siz=c[0]->siz+c[1]->siz+1;
}
void rotate(node *x)
{
node *y=x->fa; int l=(x==y->c[1]),r=l^1;
y->c[l]=x->c[r]; x->c[r]->fa=y;
x->c[r]=y; x->fa=y->fa;
if(y==y->fa->c[0]) y->fa->c[0]=x;
else y->fa->c[1]=x;
y->fa=x; y->pushup(); x->pushup();
if(root==y) root=x;
}
void splay(node *x,node *tar)
{
node *y,*z;
while(x->fa!=tar)
{
y=x->fa; z=y->fa;
if(z==tar) {rotate(x); break;}
if((x==y->c[0])^(y==z->c[0])) rotate(x);
else rotate(y); rotate(x);
}
}
void find(node *x,int y,node *z)
{
while(1)
{
if(y<=x->c[0]->siz) x=x->c[0];
else
{
y-=(x->c[0]->siz+1);
if(!y) break;
x=x->c[1];
}
}
splay(x,z);
}
ll query(int l,int r)
{
find(root,l,null);
find(root,r+2,root);
return root->c[1]->c[0]->ha;
}
void Query()
{
int x,y; scanf("%d%d",&x,&y);
int l=1,r=min(n-x+1,n-y+1)+1,mid;
while(l<r)
{
mid=(l+r)>>1;
if(query(x,x+mid-1)==query(y,y+mid-1)) l=mid+1;
else r=mid;
}
printf("%d\n",l-1);
}
void Fix()
{
int x; char y[5]; scanf("%d%s",&x,y);
find(root,x,null);
find(root,x+2,root);
root->c[1]->c[0]->w=root->c[1]->c[0]->ha=y[0]-'a';
root->c[1]->pushup();
root->pushup();
}
void Insert()
{
++n; int x; char y[5];
scanf("%d%s",&x,y);
find(root,x+1,null);
find(root,x+2,root);
root->c[1]->c[0]=new node(y[0]-'a');
root->c[1]->c[0]->fa=root->c[1];
root->c[1]->pushup();
root->pushup();
}
char st[101000];
node *build(int l,int r)
{
if(l>r) return null;
int mid=(l+r)>>1;
node *re=new node(st[mid]-'a');
re->c[0]=build(l,mid-1);
re->c[1]=build(mid+1,r);
re->c[0]->fa=re->c[1]->fa=re;
re->pushup(); return re;
}
void initialize()
{
scanf("%s",st); n=strlen(st);
scanf("%d",&m);
bin[0]=1;
for(int i=1;i<=100100;++i) bin[i]=bin[i-1]*233;
root=new node(0);
root->c[1]=new node(0);
root->c[1]->fa=root;
root->c[1]->c[0]=build(0,n-1);
root->c[1]->c[0]->fa=root->c[1];
root->c[1]->pushup();
root->pushup();
}
int main()
{
initialize();
char sw[5];
while(m--)
{
scanf("%s",sw);
switch(sw[0])
{
case 'Q': Query(); break;
case 'R': Fix(); break;
case 'I': Insert(); break;
}
}
return 0;
}