题意
维护一个由小写字母构成的字符串，要求支持单点修改，插入单个字符，查询两个后缀的\(LCP\)
思路
LCP是可以用二分+hash检验的，支持插入操作自然可以想到平衡树，由于hash可以使用线段树或者平衡树维护，所以本题平衡树+二分即可
本题需要一定卡常
Code
#include<bits/stdc++.h>
#define N 400005
using namespace std;
typedef unsigned int ULL;
const ULL tp = 1000000007;
int n,m,root;
char a[N];
ULL po[N];
struct T
{
int size,ch[2],key;
ULL val,sum;
}t[N];
int cnt;
template <class T>
void read(T &x)
{
char c;int sign=1;
while((c=getchar())>'9'||c<'0') if(c=='-') sign=-1; x=c-48;
while((c=getchar())>='0'&&c<='9') x=x*10+c-48; x*=sign;
}
inline void update(int x)
{
t[x].size=t[t[x].ch[0]].size+t[t[x].ch[1]].size+1;
t[x].sum=t[t[x].ch[1]].sum + t[x].val*po[t[t[x].ch[1]].size] + t[t[x].ch[0]].sum*po[t[t[x].ch[1]].size+1];
}
inline int add_node(int x)
{
++cnt;
t[cnt].ch[0]=t[cnt].ch[1]=0;
t[cnt].key=rand(); t[cnt].size=1;
t[cnt].sum=t[cnt].val=x;
return cnt;
}
int merge(int l,int r)
{
if(!l||!r) return l+r;
if(t[l].key<t[r].key)
{
t[l].ch[1]=merge(t[l].ch[1],r);
update(l);
return l;
}
else
{
t[r].ch[0]=merge(l,t[r].ch[0]);
update(r);
return r;
}
}
void split(int rt,int x,int &l,int &r)
{
if(!rt) {l=r=0;return;}
if(t[t[rt].ch[0]].size+1<=x) {l=rt;split(t[rt].ch[1],x-t[t[rt].ch[0]].size-1,t[rt].ch[1],r);}
else {r=rt;split(t[rt].ch[0],x,l,t[rt].ch[0]);}
update(rt);
}
inline void add(int pos,int x)//在pos后面加一个元素
{
int l,r;
split(root,pos,l,r);
root=merge(merge(l,add_node(x)),r);
}
inline void del(int pos)
{
int l,r,p;
split(root,pos-1,l,r);
split(r,1,p,r);
root=merge(l,r);
}
inline ULL ask(int x,int y)//询问hash(x,y)
{
int l,r,p;
split(root,x-1,l,r);
split(r,y-x+1,p,r);
ULL ret=t[p].sum;
root=merge(l,merge(p,r));
return ret;
}
inline int query(int x,int y)//询问LCP(x,y)
{
if(x>y) swap(x,y);
int l=1,r=n-y+1,ans=0;
while(l<=r)
{
int mid=(l+r)>>1;
if(ask(x,x+mid-1)==ask(y,y+mid-1)) l=mid+1,ans=mid;
else r=mid-1;
}
return ans;
}
int main()
{
srand((unsigned)time(NULL));srand(rand());
po[0]=1;
for(int i=1;i<=200000;++i) po[i]=po[i-1]*tp;
scanf("%s",a);
n=strlen(a);
for(int i=1;i<=n;++i) add(i-1,a[i-1]-'a'+1);//建树
read(m);
while(m--)
{
char op[2];
scanf("%s",op);
if(op[0]=='Q')//询问
{
int x,y; read(x); read(y);
printf("%d\n",query(x,y));
}
else if(op[0]=='R')//修改
{
int x; read(x); scanf("%s",op);
del(x);
add(x-1,op[0]-'a'+1);
}
else//插入
{
++n;
int x; read(x); scanf("%s",op);
add(x,op[0]-'a'+1);
}
}
return 0;
}
转载于:https://www.cnblogs.com/Chtholly/p/11426130.html
相关资源：JAVA上百实例源码以及开源项目
