[JSOI2008][BZOJ1014][JZOJ1716]火星人

题目大意

给定一个初始字符串 S ，要求支持下列操作：
∙ Q x y ：询问 suffix(x) 和 suffix(y) 的 LCP
∙ R x d ：将字符串第 x 个字符修改为字符 d
∙ I x d ：在字符串第 x 个字符后面插入字符 d

操作数 m≤1.5×105 ，其中询问操作 q 不超过 104 ，任何时候 |S|≤105
字符集 Σ 为小写拉丁字母。

---

题目分析

思路很显然， LCP 可以用二分加哈希来求，那么我们这里就使用splay来维护哈希值就好了。
时间复杂度 O(mlogn+qlog2n) 。

---

代码实现

取模太多，常数写得丑，JZOJ上垫底，BZOJ上TLE了，qwq。

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cctype>

using namespace std;

int read()
{
    int x=0,f=1;
    char ch=getchar();
    while (!isdigit(ch)) f=ch=='-'?-1:f,ch=getchar();
    while (isdigit(ch)) x=x*10+ch-'0',ch=getchar();
    return x*f;
}

int buf[30];

void write(int x)
{
    if (x<0) putchar('-'),x=-x;
    for (;x;x/=10) buf[++buf[0]]=x%10;
    if (!buf[0]) buf[++buf[0]]=0;
    for (;buf[0];putchar(buf[buf[0]--]+'0'));
}

const int MOD=998244353;
const int P=67;
const int L=100000;

int POW[L+50];
char s[L+50];
int n,q;

struct splay_tree
{
    int hash[L+50],c[L+50],fa[L+50],size[L+50];
    int son[L+50][2];
    int tot,root;

    int newnode(){return ++tot;}

    void update(int x)
    {
        size[x]=size[son[x][0]]+size[son[x][1]]+1;
        hash[x]=((hash[son[x][0]]+1ll*POW[size[son[x][0]]]*c[x]%MOD)%MOD+1ll*POW[size[son[x][0]]+1]*hash[son[x][1]]%MOD)%MOD;
    }

    bool side(int x){return son[fa[x]][1]==x;}

    void rotate(int x)
    {
        int y=fa[x];bool s=side(x);
        if (fa[y]) son[fa[y]][side(y)]=x;
        if (son[x][s^1]) fa[son[x][s^1]]=y;
        son[y][s]=son[x][s^1],son[x][s^1]=y;
        fa[x]=fa[y],fa[y]=x;
        update(y),update(x);
    }

    void splay(int x,int y)
    {
        for (;fa[x]!=y;rotate(x))
            if (fa[fa[x]]!=y)
                if (side(x)==side(fa[x])) rotate(fa[x]);
                else rotate(x);
    }

    int kth(int x,int y)
    {
        if (size[son[x][0]]+1==y) return x;
        return y<=size[son[x][0]]?kth(son[x][0],y):kth(son[x][1],y-size[son[x][0]]-1);
    }

    void split(int x,int y,int &l,int &r)
    {
        if (!y) l=0,r=x;
        else splay(l=kth(x,y),0),fa[r=son[l][1]]=0,son[l][1]=0,update(l);
    }

    void merge(int x,int y,int &rt)
    {
        if (!x) rt=y;
        else if (!y) rt=x;
        else splay(rt=kth(x,size[x]),0),fa[son[rt][1]=y]=rt,update(rt);
    }

    void insert(int x,int y)
    {
        int l,r,np;
        split(root,x,l,r),np=newnode(),c[np]=y,update(np),merge(l,np,np),merge(np,r,root);
    }

    void modify(int x,int y){splay(root=kth(root,x),0),c[root]=y,update(root);}

    int query(int l,int r)
    {
        int x,y,ret;
        split(root,r,x,y),split(x,l-1,x,root),ret=hash[root],merge(x,root,root),merge(root,y,root);
        return ret;
    }

    void init()
    {
        tot=0,root=0;
        for (int i=0,np;i<n;++i) np=newnode(),c[np]=s[i]-'a',update(np),merge(root,np,root);
    }
}t;

int LCP(int x,int y)
{
    int ret=0,l=1,r=min(n-x+1,n-y+1);
    for (int mid;l<=r;)
    {
        mid=l+r>>1;
        if (t.query(x,x+mid-1)==t.query(y,y+mid-1)) l=(ret=mid)+1;
        else r=mid-1;
    }
    return ret;
}

int main()
{
    POW[0]=1;
    for (int i=1;i<=L;++i) POW[i]=1ll*POW[i-1]*P%MOD;
    freopen("prefix.in","r",stdin),freopen("prefix.out","w",stdout);
    scanf("%s",s),n=strlen(s),t.init();
    q=read();
    for (char op;q--;)
    {
        for (op=getchar();!isalpha(op);op=getchar());
        switch (op)
        {
            case 'Q':
            {
                int x=read(),y=read();
                write(LCP(x,y)),putchar('\n');
                break;
            }
            case 'R':
            {
                int x=read();char c=getchar();
                for (;!isalpha(c);c=getchar());
                t.modify(x,c-'a');
                break;
            }
            case 'I':
            {
                int x=read();char c=getchar();
                for (;!isalpha(c);c=getchar());
                t.insert(x,c-'a'),++n;
                break;
            }
        }
    }
    fclose(stdin),fclose(stdout);
    return 0;
}