bzoj 1014: [JSOI2008]火星人prefix

.

题意：在一个字符串上，可以插入、修改，询问某两个位置开始的最长公共前缀。
题解：splay+哈希
splay维护整个字符串，记录子树哈希值。询问二分一下就可以了。
代码：

#include<bits/stdc++.h>
using namespace std;

const unsigned int base=2333;
struct pnt
{
    char c;
    unsigned int ha,sz;
    pnt *s[2],*f;
    pnt(pnt *f,char c):c(c),ha(c),f(f),sz(1)
    {
        s[0]=s[1]=0;
    }
}*root;
unsigned int Pow[100010];
int m;
char s[100010];

void pushup(pnt *x)
{
    pnt *lc=x->s[0],*rc=x->s[1];
    x->ha=x->c;
    x->sz=1;
    if(lc)
    {
        x->ha+=lc->ha*base;
        x->sz+=lc->sz;
    }
    if(rc)
    {
        x->ha=x->ha*Pow[rc->sz]+rc->ha;
        x->sz+=rc->sz;
    }
}
void rot(pnt *x)
{
    pnt *f=x->f,*ff=f->f,*r,*R;
    int w=(x==f->s[0]);
    R=f;r=x->s[w];
    R->s[w^1]=r;
    if(r)
    r->f=f;
    R=ff;r=x;
    if(R)
    R->s[f==ff->s[1]]=r;
    r->f=R;
    R=x;r=f;
    R->s[w]=r;
    r->f=R;
    pushup(f);
    pushup(x);
}
void splay(pnt *x,pnt *rt)
{
    while(x->f!=rt)
    {
        pnt *f=x->f,*ff=f->f;
        if(ff==rt)
        rot(x);
        else if((x==f->s[0])==(f==ff->s[0]))
        {
            rot(f);
            rot(x);
        }
        else
        {
            rot(x);
            rot(x);
        }
    }
    if(rt==0)
    root=x;
}
pnt* fd_by_pos(int x)
{
    pnt *now=root;
    while(1)
    {
        int ls=(now->s[0])?now->s[0]->sz:0;
        if(x<=ls)
        now=now->s[0];
        else if(x>ls+1)
        {
            x-=ls+1;
            now=now->s[1];
        }
        else
        return now;
    }
}
void ins(char c,int pos)
{
    pnt *now=fd_by_pos(pos);
    splay(now,0);
    now=now->s[1];
    while(now->s[0])
    now=now->s[0];
    pnt *p=new pnt(now,c);
    now->s[0]=p;
    pushup(now);
    splay(now,0);
}
pnt* build(char *s,int len,pnt *f)
{
    if(!len)
    return 0;
    if(len==1)
    return new pnt(f,s[0]);
    int md=len>>1;
    pnt *p=new pnt(f,s[md]);
    p->s[0]=build(s,md,p);
    p->s[1]=build(s+md+1,len-md-1,p);
    pushup(p);
    return p;
}
void chg(char c,int pos)
{
    pnt *now=fd_by_pos(pos);
    splay(now,0);
    now->c=c;
    pushup(now);
}
int get(pnt *x,pnt *y)
{
    splay(x,0);
    splay(y,x);
    if(y->s[0])
    return y->s[0]->ha;
    else
    return 0;
}
int query(int x,int y)
{
    int l=0,len=root->sz-max(x,y)+1;
    pnt *px=fd_by_pos(x-1),*py=fd_by_pos(y-1);
    while(len)
    {
        int md=l+(len>>1);
        pnt *xm=fd_by_pos(x+md),*ym=fd_by_pos(y+md);
        if(get(px,xm)==get(py,ym))
        {
            l=md+1;
            len=len-(len>>1)-1;
        }
        else
        len>>=1;
    }
    return l-1;
}
void print(pnt *x)
{
    if(!x)
    return;
    print(x->s[0]);
    printf("%c",x->c);
    print(x->s[1]);
}
int main()
{
    Pow[0]=1;
    for(int i=1;i<=100002;i++)
    Pow[i]=Pow[i-1]*base;
    scanf("%s",s+1);
    s[0]=0;
    root=build(s,strlen(s+1)+2,0);
    // print(root);
    scanf("%d",&m);
    while(m--)
    {
        char op[4];
        int x,y;
        char c[4];
        scanf("%s",op);
        if(op[0]=='Q')
        {
            scanf("%d%d",&x,&y);
            x++;y++;
            printf("%d\n",query(x,y));
        }
        else if(op[0]=='R')
        {
            scanf("%d%s",&x,c);
            x++;
            chg(c[0],x);
        }
        else
        {
            scanf("%d%s",&x,c);
            x++;
            ins(c[0],x);
        }
    }
}