[JSOI2008]火星人 hash+splay

#include<cstdio>#include<algorithm>#include<iostream>#include<cstring>#include<string>const int maxm=3000000;const int maxn=3000000; using namespace std;void setIO(string a){freopen((a+".in").c_str(),"r",stdin);}void debug(){printf("ok\n");}char str[maxn];unsigned int hash[maxm],p[maxm];int n,root;struct Splay_Tree{int ch[maxn][2],cnt_Tree,f[maxn],key[maxn],siz[maxn];#define lson ch[o][0]#define rson ch[o][1]int newnode(){return ++cnt_Tree;}int get(int x){return ch[f[x]][1]==x;} ???void pushup(int o){ ???if(!o) return ; ???siz[o]=siz[lson]+siz[rson]+1; ???hash[o]=hash[lson]+key[o]*p[siz[lson]]+hash[rson]*p[siz[lson]+1]; ???} ???void buildSplay(int l,int r,int fa,int &o){ ???if(l>r) return; ???int mid=(l+r)>>1; ???o=newnode(); ???hash[o]=key[o]=str[mid]-‘a‘; ???f[o]=fa; ?????buildSplay(l,mid-1,o,ch[o][0]); ???buildSplay(mid+1,r,o,ch[o][1]); ???pushup(o); ???} ???void rotate(int x){ ???int old=f[x],oldf=f[old],which=get(x); ???ch[old][which]=ch[x][which^1],f[ch[old][which]]=old; ???ch[x][which^1]=old,f[old]=x; ???f[x]=oldf; ???if(oldf) ???ch[oldf][ch[oldf][1]==old]=x; ???pushup(old),pushup(x);}void splay(int x,int &tar){int a=f[tar];for(int fa;(fa=f[x])!=a;rotate(x))if(f[fa]!=a) rotate(get(fa)==get(x)?fa:x);tar=x;}int findx(int pos,int o){ ????????????????????????//accurate positionif(pos<=siz[ch[o][0]]) return findx(pos,ch[o][0]);else if(pos==siz[lson]+1) return o;else return findx(pos-siz[ch[o][0]]-1,ch[o][1]);}void insert(int pos,int val){int x=findx(pos,root);splay(x,root);int y=findx(pos+1,root);splay(y,ch[root][1]);int z=ch[ch[root][1]][0]=newnode(); ??????????//betweenf[z]=ch[root][1];hash[z]=key[z]=val;pushup(z),pushup(ch[root][1]);splay(z,root);}void update(int pos,int val){splay(findx(pos,root),root);key[root]=hash[root]=val;pushup(root);}unsigned int query(int pos,int length){int x=findx(pos-1,root); ????????????????????//originsplay(x,root);int y=findx(length+1,ch[root][1]);splay(y,ch[root][1]); ???????????????????????//error!!!!int tmp=ch[root][1];return hash[ch[tmp][0]];}}T;void init(){scanf("%s",str+2);n=strlen(str+2);str[n+2]=‘a‘;str[1]=‘a‘;n+=2;p[0]=1;for(int i=1;i<maxn;++i) p[i]=p[i-1]*27;}int main(){//setIO("input");init();T.buildSplay(1,n,0,root);int m; scanf("%d",&m);while(m--){char opt[10];scanf("%s",opt);if(opt[0]==‘Q‘){int a,b;scanf("%d%d",&a,&b);if(a>b) swap(a,b);++a,++b; ???????????????????????????int l=1,r=n-b,ans=0; ???????????????????while(l<=r){int mid=(l+r)>>1;if(T.query(a,mid)==T.query(b,mid)) ans=mid,l=mid+1;else r=mid-1;}printf("%d\n",ans);continue;}char ss[10];int x,delta;scanf("%d",&x);scanf("%s",ss);delta=ss[0]-‘a‘;if(opt[0]==‘I‘) T.insert(x+1,delta),n+=1; ????//insert position: x+2 -> x+2if(opt[0]==‘R‘) T.update(x+1,delta); ????????????????????//actual position: x+1 }return 0;}