[JSOI 2008]火星人prefix - Anonymity - 454251

记录编号	454251	评测结果	AAAAAAAAAA
题目名称	[JSOI 2008]火星人prefix	最终得分	100
用户昵称	Anonymity	是否通过	通过
代码语言	C++	运行时间	2.980 s
提交时间	2017-09-28 18:37:44	内存使用	1.17 MiB
显示代码纯文本
#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <cstring>
#define maxn 100005
using namespace std;
inline int read()
{   char c=getchar();int x=0,y=1;
    while(c<'0'||c>'9'){if(c=='-') y=-1;c=getchar();}
    while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
    return x*y;
}
inline char readchar(){char c;for(c=getchar();c<'a'||c>'z';c=getchar());return c;}
inline char readop(){char c;for(c=getchar();c!='Q'&&c!='R'&&c!='I';c=getchar());return c;}
template<typename T>
inline T m_min(T x,T y){return x<y?x:y;}
const int P=123;
typedef unsigned int ull;
char T[maxn];
int len,m;
ull H[maxn],xp[maxn];
struct Treap
{   Treap *ch[2];int s,r;ull Hash,v;
    Treap(ull x=0):v(x),Hash(x),r(rand()),s(1){ch[0]=ch[1]=NULL;}
    inline int sz(){return this?this->s:0;}
    inline ull hv(){return this?this->Hash:0;}
    inline void mt()
    {   if(!this) return;
        this->s=this->ch[0]->sz()+this->ch[1]->sz()+1;
        this->Hash=this->ch[0]->hv()+this->v*xp[this->ch[0]->sz()]+this->ch[1]->hv()*xp[this->ch[0]->sz()+1];
    }
    inline void paint(ull x){if(this){this->v=this->Hash=x;}}
}*root;
typedef pair<Treap*,Treap*> dt;
inline Treap* merge(Treap* x,Treap* y)
{   if(!x) return y;if(!y) return x;
    if(x->r < y->r){x->ch[1]=merge(x->ch[1],y);x->mt();return x;}
    else{y->ch[0]=merge(x,y->ch[0]);y->mt();return y;}
}
inline dt split(Treap* x,int k)
{   if(!x) return dt(NULL,NULL);if(!k) return dt(NULL,x);
    dt y;
    if(x->ch[0]->sz()>=k) y=split(x->ch[0],k),x->ch[0]=y.second,x->mt(),y.second=x;
    else y=split(x->ch[1],k-x->ch[0]->sz()-1),x->ch[1]=y.first,x->mt(),y.first=x;
    return y;
}
inline Treap* build(char* s,int y)
{   Treap* *st=new Treap*[len];Treap *las,*x,*ans;int tail=0;
    for(int i=1;i<=y;++i)
    {   x=new Treap(s[i]-'a');las=NULL;
        while(tail&&st[tail-1]->r > x->r)
            st[tail-1]->mt(),las=st[tail-1],st[--tail]=NULL;
        if(tail) st[tail-1]->ch[1]=x;
        x->ch[0]=las;st[tail++]=x;
    }
    while(tail) st[--tail]->mt();
    ans=st[0];
    delete []st;
    return ans;
}
inline ull getmes(int x,int y)
{   dt t1=split(root,y),t2=split(t1.first,x-1);
    ull tmp=t2.second->hv();root=merge(merge(t2.first,t2.second),t1.second);
    return tmp;
}
inline int query(int x,int y)
{   if(x==y) return len-x+1;
    int rig=m_min(len-x+1,len-y+1),lef=0,mid,ans=0;
    while(lef<=rig)
    {   mid=lef+rig>>1;
        if(getmes(x,x+mid-1)==getmes(y,y+mid-1)) ans=mid,lef=mid+1;
        else rig=mid-1;
    }
    return ans;
}
inline void change(int x,ull y)
{   dt t1=split(root,x-1),t2=split(t1.second,1);
    t2.first->paint(y);
    root=merge(t1.first,merge(t2.first,t2.second));
}
inline void insert(int x,ull y)
{   Treap* tmp=new Treap(y);
    dt t1=split(root,x);root=merge(merge(t1.first,tmp),t1.second);
}
int main()
{   freopen("bzoj_1014.in","r",stdin);
    freopen("bzoj_1014.out","w",stdout);
    scanf("%s",T+1);m=read();len=strlen(T+1);xp[0]=1;
    for(int i=1;i<=100000;++i) xp[i]=xp[i-1]*P;
    root=build(T,len);int x,y;char z;
    for(int i=1;i<=m;++i)
    {   z=readop();
        if(z=='Q'){x=read();y=read();printf("%d\n",query(x,y));}
        else if(z=='R'){x=read();z=readchar();change(x,z-'a');}
        else{x=read();z=readchar();insert(x,z-'a');++len;}
    }
    return 0;
}