BZOJ1014 JSOI2008 火星人prefix

---

Description

　　火星人最近研究了一种操作：求一个字串两个后缀的公共前缀。比方说，有这样一个字符串：madamimadam，我们将这个字符串的各个字符予以标号：序号： 1 2 3 4 5 6 7 8 9 10 11 字符 m a d a m i m a d a m 现在，火星人定义了一个函数LCQ(x, y)，表示：该字符串中第x个字符开始的字串，与该字符串中第y个字符开始的字串，两个字串的公共前缀的长度。比方说，LCQ(1, 7) = 5, LCQ(2, 10) = 1, LCQ(4, 7) = 0 在研究LCQ函数的过程中，火星人发现了这样的一个关联：如果把该字符串的所有后缀排好序，就可以很快地求出LCQ函数的值；同样，如果求出了LCQ函数的值，也可以很快地将该字符串的后缀排好序。 尽管火星人聪明地找到了求取LCQ函数的快速算法，但不甘心认输的地球人又给火星人出了个难题：在求取LCQ函数的同时，还可以改变字符串本身。具体地说，可以更改字符串中某一个字符的值，也可以在字符串中的某一个位置插入一个字符。地球人想考验一下，在如此复杂的问题中，火星人是否还能够做到很快地求取LCQ函数的值。

Input

　　第一行给出初始的字符串。第二行是一个非负整数M，表示操作的个数。接下来的M行，每行描述一个操作。操作有3种，如下所示

1、询问。语法：Qxy，x,y均为正整数。功能：计算LCQ(x,y)限制：1<=x,y<=当前字符串长度。

2、修改。语法：Rxd，x是正整数，d是字符。功能：将字符串中第x个数修改为字符d。限制：x不超过当前字符串长度。

3、插入：语法：Ixd，x是非负整数，d是字符。功能：在字符串第x个字符之后插入字符d，如果x=0，则在字符串开头插入。限制：x不超过当前字符串长度

Output

　　对于输入文件中每一个询问操作，你都应该输出对应的答案。一个答案一行。

Sample Input

madamimadam

7

Q 1 7

Q 4 8

Q 10 11

R 3 a

Q 1 7

I 10 a

Q 2 11

Sample Output

5

1

0

2

1

HINT

1、所有字符串自始至终都只有小写字母构成。

2、M<=150,000

3、字符串长度L自始至终都满足L<=100,000

4、询问操作的个数不超过10,000个。

对于第1，2个数据，字符串长度自始至终都不超过1,000

对于第3，4，5个数据，没有插入操作。

---

我们发现有修改和添加字符的操作，就想到了平衡树

又因为我比较喜欢非旋转Treap

然后就写了一波

注意这里的Treap不能按照字符的大小来建树，我们应该根据字符串中字符的先后顺序来建树，添加字符就直接在第k个位置后面添加就好了，修改比较常规，直接先分裂再合并就行了

现在我们考虑怎么求字符串的两个后缀的最长公共前缀，首先如果没有修改和添加操作我们肯定会选择后缀数组，但现在我们有了修改和添加操作，所以我们需要换一种方式思考。在一般情况下，字符串的hash值是否相同可以判断字符串是否相同，所以我们可以用hash，但是如果这样暴力判断，时间效率依旧不优秀，达到O(n2logn)" role="presentation">O(n2logn)O(n2logn)，那么我们可以发现这个hash段的长度是具有二分性的，所以我们就可以用二分来查询，就可以将时间优化成O(nlog2n)" role="presentation">O(nlog2n)O(nlog2n)

那么我们怎么维护hash呢，首先，在Treap上进行向上更新操作的时候可以通过合并左右区间hash值来维护，那么我们就需要与处理base偏移量（pow数组），然后通过

hash[t]=hash[ls[t]]+pow[siz[ls[t]]]∗val[t]+pow[siz[ls[t]]+1]∗hash[rs[t]]" role="presentation">hash[t]=hash[ls[t]]+pow[siz[ls[t]]]∗val[t]+pow[siz[ls[t]]+1]∗hash[rs[t]]hash[t]=hash[ls[t]]+pow[siz[ls[t]]]∗val[t]+pow[siz[ls[t]]+1]∗hash[rs[t]]

来计算当前节点为根的子树hash值，其中val是当前节点所代表的字符的编号（字符-‘a’+1）

然后我们在二分的时候直接剥离出从x、y开始长度为len的子树就好了

---

#include<bits/stdc++.h>

using namespace std;

#define N 1000010

#define Base 37

typedef pair<int,int> pi;

struct Treap{

    int tot,root,n;

    int siz[N],key[N],ls[N],rs[N],val[N];

    unsigned int hash[N],pow[N];

    void init(){

        tot=root=0;

        pow[0]=1;

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

            pow[i]=pow[i-1]*Base;

    }

    int new_treap_point(int vl){

        int newt=++tot;

        siz[newt]=1;

        hash[newt]=val[newt]=vl;

        key[newt]=rand();

        ls[newt]=rs[newt]=0;

        return newt;

    }

    void update(int t){

        siz[t]=siz[ls[t]]+siz[rs[t]]+1;

        hash[t]=hash[ls[t]]+pow[siz[ls[t]]]*val[t]+pow[siz[ls[t]]+1]*hash[rs[t]];

    }

    int merge(int a,int b){

        if(!a)return b;

        if(!b)return a;

        if(key[a]<key[b]){

            rs[a]=merge(rs[a],b);

            update(a);return a;

        }else{

            ls[b]=merge(a,ls[b]);

            update(b);return b;

        }

    }

    pi split(int t,int k){

        if(!t)return pi(0,0);

        pi ans;

        if(siz[ls[t]]>=k){

            pi tmp=split(ls[t],k);

            ls[t]=tmp.second;

            update(t);

            ans.first=tmp.first;

            ans.second=t;

        }else{

            pi tmp=split(rs[t],k-siz[ls[t]]-1);

            rs[t]=tmp.first;

            update(t);

            ans.first=t;

            ans.second=tmp.second;

        }

        return ans;

    }

    void insert(int k,int vl){

        pi x=split(root,k);

        int t=new_treap_point(vl);

        root=merge(merge(x.first,t),x.second);

    }

    void erase(int k){

        pi x=split(root,k);

        root=merge(split(x.first,k-1).first,x.second);

    }

    void modify(int k,int vl){

        erase(k);

        insert(k-1,vl);

    }

    int queryhash(int t,int len){

        if(t+len-1>siz[root])return -1;

        pi x=split(root,t-1);

        pi y=split(x.second,len);

        int ans=hash[y.first];

        root=merge(x.first,merge(y.first,y.second));

        return ans;

    }

    int query(int x,int y){

        int l=0,r=N,ans=0;

        while(l<=r){

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

            int px=queryhash(x,mid),py=queryhash(y,mid);

            if(px==-1||py==-1){r=mid-1;continue;}

            if(px==py)ans=mid,l=mid+1;

            else r=mid-1;

        }

        return ans;

    }

}treap;

int n,m;

char s[N],c[5];

int main(){

    srand(time(0));

    treap.init();

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

    n=strlen(s+1);

    treap.n=n;

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

        treap.root=treap.merge(treap.root,treap.new_treap_point(s[i]-'a'+1));

    scanf("%d",&m);

    while(m--){

        scanf("%s",c);

        if(c[0]=='Q'){

            int x,y;scanf("%d%d",&x,&y);

            printf("%d\n",treap.query(x,y));

        }else if(c[0]=='I'){

            int x;scanf("%d%s",&x,c);

            treap.insert(x,c[0]-'a'+1);

        }else{

            int x;scanf("%d%s",&x,c);

            treap.modify(x,c[0]-'a'+1);

        }

    }

    return 0;

}