前两篇讲述了SPLAY模板操作，这一篇稍微介绍一下SPLAY的实际应用

（其实只有一道题，因为本蒟蒻就写了这一个）

例：bzoj 1014火星人prefix

由于本蒟蒻不会后缀数组，所以题目中给的提示完全没看懂

不过并不影响我们做这道题，因为正解好像不用后缀数组...

首先，如果这题没有插入和修改，那么我们只需二分+hash即可

（很显然，二分相同前缀的长度，用hash检查是否合法）

可是这题有插入修改，单纯hash搞不了

所以我们应用SPLAY维护hash值即可

查找时同样二分

#include <cstdio>

#include <cmath>

#include <cstring>

#include <cstdlib>

#include <iostream>

#include <algorithm>

#include <queue>

#include <stack>

#define ls tree[rt].lson

#define rs tree[rt].rson

#define ull unsigned int

#define seed 131

#define maxn 150000

using namespace std;

struct SPLAY

{

    int lson;

    int rson;

    ull val;

    ull typval;

    int huge;

    int fa;

}tree[150005];

ull p[150005];

int n,m;

char s[150005];

int cot=0;

int rot;

char tt[2];

void update(int rt)

{

    tree[rt].huge=tree[ls].huge+tree[rs].huge+1;

    tree[rt].val=tree[ls].val+p[tree[ls].huge+1]*tree[rs].val+tree[rt].typval*p[tree[ls].huge];

}

void buildtree(int l,int r,int f)

{

    int mid=(l+r)>>1;

    if(l==r)

    {

        tree[l].lson=tree[l].rson=0;

        tree[l].typval=tree[l].val=s[l]-'a'+1;

        tree[l].huge=1;

        tree[l].fa=f;

    }

    tree[mid].typval=s[mid]-'a'+1;

    tree[mid].fa=f;

    if(l<mid)

    {

        buildtree(l,mid-1,mid);

    }

    if(r>mid)

    {

        buildtree(mid+1,r,mid);

    }

    update(mid);

    if(mid<f)

    {

        tree[f].lson=mid;

    }else

    {

        tree[f].rson=mid;

    }

}

void rotate(int st,int &ed)

{

    int v1=tree[st].fa;

    int v2=tree[v1].fa;

    int ltyp;

    if(tree[v1].lson==st)

    {

        ltyp=0;

    }else

    {

        ltyp=1;

    }

    if(v1==ed)

    {

        ed=st;

    }else

    {

        if(tree[v2].lson==v1)

        {

            tree[v2].lson=st;

        }else

        {

            tree[v2].rson=st;

        }

    }

    if(ltyp)

    {

        tree[tree[st].lson].fa=v1;

        tree[v1].fa=st;

        tree[v1].rson=tree[st].lson;

        tree[st].lson=v1;

        tree[st].fa=v2;

    }else

    {

        tree[tree[st].rson].fa=v1;

        tree[v1].fa=st;

        tree[v1].lson=tree[st].rson;

        tree[st].rson=v1;

        tree[st].fa=v2;

    }

    update(v1);

    update(st);

}

void splay(int st,int &ed)

{

    while(st!=ed)

    {

        int v1=tree[st].fa;

        int v2=tree[v1].fa;

        if(v1!=ed)

        {

            if((tree[v1].lson==st&&tree[v2].lson!=v1)||(tree[v1].rson==st&&tree[v2].rson!=v1))

            {

                rotate(st,ed);

            }else

            {

                rotate(v1,ed);

            }

        }

        rotate(st,ed);

    }

}

int findf(int rt,int v)

{

    if(tree[ls].huge+1==v)

    {

        return rt;

    }else if(tree[ls].huge>=v)

    {

        return findf(ls,v);

    }else

    {

        return findf(rs,v-1-tree[ls].huge);

    }

}

int split(int st,int ed)

{

    int v1=findf(rot,st);

    int v2=findf(rot,ed);

    splay(v1,rot);

    splay(v2,tree[v1].rson);

    return tree[v2].lson;

}

bool check(int st1,int st2,int len)

{

    int v1=split(st1,st1+len+1);

    ull tt=tree[v1].val;

    int v2=split(st2,st2+len+1);

    ull ty=tree[v2].val;

    if(tt==ty)

    {

        return 1;

    }else

    {

        return 0;

    }

}

void ins(int st,int ed,int v)

{

    int v1=split(st,ed);

    tree[v1].typval=tree[v1].val=v;

    update(tree[v1].fa);

    update(tree[tree[v1].fa].fa);

}

void change(int st,int v)

{

    int v1=findf(rot,st);

    int v2=findf(rot,st+1);

    splay(v1,rot);

    splay(v2,tree[rot].rson);

    cot++;

    tree[cot].typval=tree[cot].val=v;

    tree[cot].huge=1;

    tree[v2].lson=cot;

    tree[cot].fa=v2;

    update(v2);

    update(v1);

}

int divi(int lc,int rc,int st1,int st2)

{

    int l=lc,r=rc;

    while(l<=r)

    {

        int mid=(l+r)>>1;

        if(check(st1,st2,mid))

        {

            l=mid+1;

        }else

        {

            r=mid-1;

        }

    }

    return r;

}

int main()

{

    scanf("%s",s+2);

    int l=strlen(s+2);

    scanf("%d",&m);

    p[0]=1;

    for(int i=1;i<=maxn;i++)

    {

        p[i]=p[i-1]*seed;

    }

    buildtree(1,l+2,0);

    cot=l+2;

    rot=(l+3)>>1;

    while(m--)

    {

        scanf("%s",tt);

        if(tt[0]=='Q')

        {

            int lq,rq;

            scanf("%d%d",&lq,&rq);

            printf("%d\n",divi(1,min(cot-lq-1,cot-rq-1),lq,rq));

        }else if(tt[0]=='R')

        {

            int x;

            scanf("%d",&x);

            scanf("%s",tt);

            int d=tt[0]-'a'+1;

            ins(x,x+2,d);

        }else

        {

            int x;

            scanf("%d",&x);

            scanf("%s",tt);

            int d=tt[0]-'a'+1;

            change(x+1,d);

        }

    }

    return 0;

}