题目大意
就是给你一个字符串，有三种操作，共\(m\)个
\(Q~x~y\)：询问第\(x\)个后缀和第\(y\)个后缀的LCP
\(R~x~y\)：把第\(x\)个字符改成\(y\)
\(I~x~y\)：在第\(x\)个字符后面插入一个字符\(y\)
\(m\leq 150000,\)任何时候字符串长度\(\leq 100000\)，询问个数\(\leq 10000\)
题解
直接用平衡树维护哈希值，询问时二分答案。我用unsigned long long存回TLE，用unsigned存就能过。
时间复杂度：\(O(q\log^2n+m\log n)\)（\(q\)为询问个数）
代码
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<ctime>
#include<utility>
using namespace std;
typedef long long ll;
typedef unsigned ui;
typedef pair<int,int> pii;
struct node
{
int v;
int k;
int ls,rs;
int sz;
ui s;
node()
{
v=k=ls=rs=sz=0;
s=0;
}
};
node a[1000010];
int cnt=0;
ui pw[1000010];
int newnode(int v)
{
cnt++;
a[cnt].v=v;
a[cnt].k=rand();
a[cnt].s=v;
a[cnt].sz=1;
return cnt;
}
void mt(int p)
{
a[p].s=a[a[p].ls].s*pw[a[a[p].rs].sz+1]+a[p].v*pw[a[a[p].rs].sz]+a[a[p].rs].s;
a[p].sz=a[a[p].ls].sz+a[a[p].rs].sz+1;
}
int merge(int x,int y)
{
if(!x||!y)
return x+y;
if(a[x].k<a[y].k)
{
a[x].rs=merge(a[x].rs,y);
mt(x);
return x;
}
else
{
a[y].ls=merge(x,a[y].ls);
mt(y);
return y;
}
}
pii split(int x,int v)
{
if(!x)
return pii();
if(v<=a[a[x].ls].sz)
{
pii s=split(a[x].ls,v);
a[x].ls=s.second;
s.second=x;
mt(x);
return s;
}
else
{
pii s=split(a[x].rs,v-a[a[x].ls].sz-1);
a[x].rs=s.first;
s.first=x;
mt(x);
return s;
}
}
char s[1000010];
int rt=0;
int n;
ui gethash(int l,int r)
{
if(l>r)
return 0;
pii s1=split(rt,r);
pii s2=split(s1.first,l-1);
ui res=a[s2.second].s;
s1.first=merge(s2.first,s2.second);
rt=merge(s1.first,s1.second);
return res;
}
int query(int x,int y)
{
int l=0;
int r=min(n-x+1,n-y+1);
while(l<r)
{
int mid=(l+r+1)>>1;
if(gethash(x,x+mid-1)==gethash(y,y+mid-1))
l=mid;
else
r=mid-1;
}
return l;
}
void insert(int x,int v)
{
pii s1=split(rt,x);
s1.first=merge(s1.first,newnode(v));
rt=merge(s1.first,s1.second);
n++;
}
void change(int x,int v)
{
pii s1=split(rt,x);
pii s2=split(s1.first,x-1);
a[s2.second].s=a[s2.second].v=v;
s1.first=merge(s2.first,s2.second);
rt=merge(s1.first,s1.second);
}
int main()
{
freopen("bzoj1014.in","r",stdin);
freopen("bzoj1014.out","w",stdout);
srand(12700);
int i,m;
pw[0]=1;
for(i=1;i<=1000000;i++)
pw[i]=pw[i-1]*127;
scanf("%s",s+1);
n=strlen(s+1);
for(i=1;i<=n;i++)
rt=merge(rt,newnode(s[i]-'a'+1));
scanf("%d",&m);
int x,y;
for(i=1;i<=m;i++)
{
scanf("%s",s+1);
if(s[1]=='Q')
{
scanf("%d%d",&x,&y);
printf("%d\n",query(x,y));
}
else if(s[1]=='R')
{
scanf("%d%s",&x,s+1);
change(x,s[1]-'a'+1);
}
else
{
scanf("%d%s",&x,s+1);
insert(x,s[1]-'a'+1);
}
}
return 0;
}