[bzoj1014]：[JSOI2008]火星人prefix

本文主要是介绍[bzoj1014]：[JSOI2008]火星人prefix，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

传送门
这个题我一眼秒，然后发现好像是查询好像变成了 $O(log^2n)$
然后发现数据范围说查询操作不超过10000次，然后就觉得应该是正解了。。
然后调试了超级久。。。
再然后就WA了3个点。。
最后发现我调试的时候为了方便，质数只取到了1000，然后取到1e9+7，就过了。。
我们来说正解吧。

emmmm，一句话题解吧。
Splay+Hash+二分
好像有点儿少，还是具体说说吧。。
首先，因为有插入操作，还有修改，还有查询，所以肯定要用Splay
具体用法的话可以参考NOI2005维修数列
然后还有字符串Hash，正常Hash就好了，出题人没有卡Hash。
（注意，这个题时间比较紧，不要取模，自然溢出就好了）
然后查询的时候，我们只要二分一个答案mid
然后判断[x,x+mid-1]和[y,y+mid-1]这两段的Hash值是否相同就好了
相同，则l=mid
不相同，则r=mid-1
然后取mid的时候要这样取mid=(l+r+1)>>1
然后还要while(l < r)
最后返回l
不要问我怎么知道这么做的
（其实是试出来的）
代码：

#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstdlib>
#define ll unsigned long long
using namespace std;
inline int read(){int x=0;char ch=' ';int f=1;while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();if(ch=='-')f=-1,ch=getchar();while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();return x*f;
}
const int N=2e5+5;
const ll p=1e9+7;
char cc[N];
int n,m,sz,root;
int f[N],ch[N][2];
ll fac[N],val[N],sum[N],size[N];
inline void pushup(int x){int lc=ch[x][0],rc=ch[x][1];sum[x]=sum[lc]*(fac[size[rc]+1])+sum[rc]+val[x]*fac[size[rc]];size[x]=size[lc]+size[rc]+1;
}
inline bool get(int x){return ch[f[x]][1]==x;}
inline void rotate(int x){int y=f[x],z=f[y],w=get(x),w2=get(y);ch[y][w]=ch[x][w^1];f[ch[y][w]]=y;ch[x][w^1]=y;f[y]=x;f[x]=z;if(z)ch[z][w2]=x;pushup(y);pushup(x);
}
inline void splay(int x,int goal){// cout<<"splay "<<x<<" to "<<goal<<endl;for(int fa=0;(fa=f[x])!=goal;rotate(x))if(f[fa]!=goal)rotate((get(fa)==get(x))?fa:x);if(!goal)root=x;// cout<<"   success!"<<endl;
}
inline void build(int &x,int l,int r,int fa){if(l>r){x=0;return;}int mid=(l+r)>>1;x=++sz;val[sz]=sum[sz]=cc[mid-1]-'a'+1;size[sz]=1;f[sz]=fa;if(mid==1)val[sz]=sum[sz]=0;if(mid==n+2)val[sz]=sum[sz]=0;if(!(l^r))return;build(ch[x][0],l,mid-1,x);build(ch[x][1],mid+1,r,x);pushup(x);
}
inline int kth(int k){int now=root;while(1){if(ch[now][0]&&k<=size[ch[now][0]])now=ch[now][0];else{int tmp=size[ch[now][0]]+1;if(k<=tmp){return now;}k-=tmp;now=ch[now][1];}}
}
inline void print(int);
inline int split(int L,int R){if(L>R)return 0;L++;R++;// cout<<"split "<<L-1<<' '<<R-1<<endl;int l=kth(L-1);splay(l,0);int r=kth(R+1);splay(r,l);// cout<<l<<' '<<r<<endl;// cout<<"   success!"<<endl;// print(root);return ch[r][0];
}
inline ll query(int L,int R){int now=split(L,R);return sum[now];
}
inline void insert(int pos,char c){n++;int now=split(pos,pos);val[++sz]=sum[sz]=c-'a'+1;size[sz]=1;f[sz]=now;ch[now][1]=sz;pushup(now);pushup(ch[root][1]);pushup(root);// print(root);
}
inline void change(int pos,char c){int now=split(pos,pos);val[now]=sum[now]=c-'a'+1;size[now]=1;pushup(ch[root][1]);pushup(root);
}
inline int find(int x,int y){if(x>y)swap(x,y);ll pre1=query(x,x);ll pre2=query(y,y);if(pre1!=pre2)return 0;int l=1,r=n-y+1,mid;while(l<r){// cout<<"find "<<l<<' '<<r<<endl;mid=(l+r+1)>>1;ll v1=query(x,x+mid-1);// cout<<v1<<' ';ll v2=query(y,y+mid-1);// cout<<v2<<endl;if(v1==v2)l=mid;else r=mid-1;// system("pause");}return l;
}
inline void print(int now){cout<<endl;cout<<"id:  "<<now<<endl;cout<<"val: "<<val[now]<<endl;cout<<"sum: "<<sum[now]<<endl;cout<<"fa:  "<<f[now]<<endl;cout<<"lc:  "<<ch[now][0]<<endl;cout<<"rc:  "<<ch[now][1]<<endl;cout<<endl;// system("pause");if(ch[now][0])print(ch[now][0]);if(ch[now][1])print(ch[now][1]);
}
int main(){scanf("%s",cc+1);m=read();n=strlen(cc+1);fac[0]=1;for(int i=1;i<N;i++)fac[i]=fac[i-1]*p;build(root,1,n+2,0);sz=n+2;// print(root);while(m--){int x,y;char opt[3],c[3];scanf("%s",opt);if(opt[0]=='Q')x=read(),y=read(),printf("%d\n",find(x,y));if(opt[0]=='R')x=read(),scanf("%s",c),change(x,c[0]);if(opt[0]=='I')x=read(),scanf("%s",c),insert(x,c[0]);}return 0;
}