![bzoj1014: [JSOI2008]火星人prefix splay+hash+二分](https://image.shishitao.com:8440/aHR0cHM6Ly9ia3FzaW1nLmlrYWZhbi5jb20vdXBsb2FkL2NoYXRncHQtcy5wbmc%2FIQ%3D%3D.png?!?w=700&webp=1 "bzoj1014: [JSOI2008]火星人prefix splay+hash+二分")
Description
火星人最近研究了一种操作：求一个字串两个后缀的公共前缀。比方说，有这样一个字符串：madamimadam，
我们将这个字符串的各个字符予以标号：序号： 1 2 3 4 5 6 7 8 9 10 11 字符 m a d a m i m a d a m 现在，
火星人定义了一个函数LCQ(x, y)，表示：该字符串中第x个字符开始的字串，与该字符串中第y个字符开始的字串
，两个字串的公共前缀的长度。比方说，LCQ(1, 7) = 5, LCQ(2, 10) = 1, LCQ(4, 7) = 0 在研究LCQ函数的过程
中，火星人发现了这样的一个关联：如果把该字符串的所有后缀排好序，就可以很快地求出LCQ函数的值；同样，
如果求出了LCQ函数的值，也可以很快地将该字符串的后缀排好序。 尽管火星人聪明地找到了求取LCQ函数的快速
算法，但不甘心认输的地球人又给火星人出了个难题：在求取LCQ函数的同时，还可以改变字符串本身。具体地说
，可以更改字符串中某一个字符的值，也可以在字符串中的某一个位置插入一个字符。地球人想考验一下，在如此
复杂的问题中，火星人是否还能够做到很快地求取LCQ函数的值。
Input
第一行给出初始的字符串。第二行是一个非负整数M，表示操作的个数。接下来的M行，每行描述一个操作。操
作有3种，如下所示
1、询问。语法：Qxy，x,y均为正整数。功能：计算LCQ(x,y)限制：1<=x,y<=当前字符串长度。
2、修改。语法：Rxd，x是正整数，d是字符。功能：将字符串中第x个数修改为字符d。限制：x不超过当前字
符串长度。
3、插入：语法：Ixd，x是非负整数，d是字符。功能：在字符串第x个字符之后插入字符d，如果x=0，则在字
符串开头插入。限制：x不超过当前字符串长度
题解：splay维护区间hash值，每次查询对答案二分，然后O（1）判断相不相等，注意考虑split时l，r为边界的情况
/**************************************************************
Problem: 1014
User: walfy
Language: C++
Result: Accepted
Time:6708 ms
Memory:7424 kb
****************************************************************/ //#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast,no-stack-protector")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pi acos(-1.0)
#define ll long long
#define vi vector<int>
#define mod 1000000007
#define C 0.5772156649
#define ls l,m,rt<<1
#define rs m+1,r,rt<<1|1
#define pil pair<int,ll>
#define pli pair<ll,int>
#define pii pair<int,int>
#define cd complex<double>
#define ull unsigned long long
#define base 1000000000000000000
#define fio ios::sync_with_stdio(false);cin.tie(0) using namespace std; const double g=10.0,eps=1e-;
const int N=+,maxn=+,inf=0x3f3f3f3f,INF=0x3f3f3f3f3f3f3f3f;
const ull bs=; char a[N];
ull p[N];
struct Splay{
struct Node{
Node *ch[];
int v,s;ull ha;
int cmp(int x)const{
int d = x - ch[]->s;
if(d==)return -;
return d<=?:;
}
};
inline void maintain(Node *o)
{
o->s = + o->ch[]->s+o->ch[]->s;
o->ha = o->v;
if(o->ch[]!=null)
{
o->ha=o->ha+o->ch[]->ha*bs;
}
if(o->ch[]!=null)
{
o->ha=o->ha*p[o->ch[]->s]+o->ch[]->ha;
}
}
Node *null;
inline void Rotate(Node* &o,int d)
{
Node* k = o->ch[d^];
o->ch[d^] = k->ch[d];
k->ch[d] = o;
maintain(o);maintain(k);
o = k;
}
inline void splay(Node* &o,int k)
{
int d = o->cmp(k);
if(d==)k-=o->ch[]->s+;
if(d!=-)
{
Node* p=o->ch[d];
int d2=p->cmp(k);
int k2=(d2==?k:k-p->ch[]->s-);
if(d2!=-)
{
splay(p->ch[d2],k2);
if(d==d2)Rotate(o,d^);
else Rotate(o->ch[d],d);
}
Rotate(o,d^);
}
}
inline Node* Merge(Node* left,Node* right)
{
splay(left,left->s);
left->ch[]=right;
maintain(left);
return left;
}
inline void split(Node* o,int k,Node* &left,Node* &right)
{
splay(o,k);
right = o->ch[];
o->ch[]=null;
left=o;
maintain(left);
}
Node *root,*left,*right;
inline void init(int sz)
{
null = new Node;
null->s=;
root = new Node;
root->v=(int)a[]-'a';root->s=;
root->ch[]=root->ch[]=null;
maintain(root);
Node* p;
for(int i=;i<=sz;i++)
{
p = new Node;
p->v=a[i]-'a';p->s=;
p->ch[]=root;p->ch[]=null;
root=p;
maintain(root);
}
// debug(root);
}
inline void ins()
{
int x;char c[];
scanf("%d%s",&x,c);
Node* p=new Node;
p->v=(int)(c[]-'a');p->s=;
p->ch[]=p->ch[]=null;
if(x==)
{
root=Merge(p,root);
}
else
{
split(root,x,left,right);
root=Merge(Merge(left,p),right);
}
}
inline ull getans(int l,int r)
{
ull ans=;
if(l==&&r==root->s)ans=root->ha;
else if(l==)
{
split(root,r,left,right);
ans=left->ha;
root=Merge(left,right);
}
else if(r==root->s)
{
split(root,l-,left,right);
ans=right->ha;
//printf("%lld\n",right->ha);
root=Merge(left,right);
}
else
{
split(root,r,left,right);
Node *tel,*ter;
split(left,l-,tel,ter);
ans=ter->ha;
root=Merge(Merge(tel,ter),right);
}
//printf("%d %d %lld\n",l,r,ans);
return ans;
}
inline void query()
{
int x,y;scanf("%d%d",&x,&y);
if(x>y)swap(x,y);
int n=root->s;
int l=,r=n-y+;
while(l<r-)
{
//printf("%d %d %lld %d %d %lld\n",x,x+m-1,getans(x,x+m-1),y,y+m-1,getans(y,y+m-1));
int m=(l+r)>>;
ull te1=getans(x,x+m-),te2=getans(y,y+m-);
if(te1==te2)l=m;
else r=m;
}
printf("%d\n",l);
}
inline void debug(Node* o)
{
if(o->ch[]!=null)debug(o->ch[]);
printf("%d %lld %d\n",o->v,o->ha,o->s);
if(o->ch[]!=null)debug(o->ch[]);
}
}sp;
int main()
{
p[]=;
for(int i=;i<N;i++)p[i]=p[i-]*bs;
scanf("%s",a+);
int len=strlen(a+);
// for(int i=1;i<=len;i++)printf("%d ",a[i]-'a');puts("");
sp.init(len);
int m;scanf("%d",&m);
while(m--)
{
char op[];
scanf("%s",op);
if(op[]=='Q')sp.query();
else if(op[]=='R')
{
int x;char c[];
scanf("%d%s",&x,c);
sp.split(sp.root,x,sp.left,sp.right);
sp.left->v=(int)c[]-'a';
sp.root=sp.Merge(sp.left,sp.right);
}
else sp.ins();
}
return ;
}
/***********************
998244353
***********************/