[BZOJ 1014] [JSOI2008]火星人prefix

Posted on | Edited on | In , | Views:

题目链接

BZOJ 1014

做法

一眼看过去，这不是$SAM$模板题吗。
再一眼，什么，还有插入和修改，那好吧，换个做法。
$LCQ$和我们熟知的$LCP$本质上是一样的，有一个经典做法就是二分+哈希。
所以我们可以用一棵平衡树来维护整个序列的哈希值。
具体做法：
以在序列中的位置作为关键字构建平衡树
平衡树的每个节点维护他子树的哈希值，实际上就是序列一段的哈希值。
令右子树的$size$为$R$
$hash[u]=hash[lson[u]]base^{R+1}+data[u]base^R+hash[rson[u]]$
这样当我们想要查询一段区间的哈希值时只要把整段区间从平衡树里拿出来就好了。
插入和修改用平衡树可以实现。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
#include<cstdio>
#include<algorithm>
#include<cctype>
#include<cstring>
#include<iostream>
#include<cmath>
#define LL long long
#define N (100005)
using namespace std;
int n,base=31,len,cnt,root,x,y;
unsigned int mi[N];
char c[N],op[5],a[5];
template <typename T> void read(T&t) {
    t=0;
    bool fl=true;
    char p=getchar();
    while (!isdigit(p)) {
        if (p=='-') fl=false;
        p=getchar();
    }
    do {
        (t*=10)+=p-48;p=getchar();
    }while (isdigit(p));
    if (!fl) t=-t;
}
struct node{
    unsigned int hash;
    int ls,rs,val,size,heap;
}T[N]; 
struct two{
    int ls,rs;
};
inline void update(int u){
    int R=T[T[u].rs].size;
    T[u].hash=T[T[u].ls].hash*mi[R+1]+T[u].val*mi[R]+T[T[u].rs].hash;
    T[u].size=T[T[u].ls].size+T[T[u].rs].size+1;
}
inline two split(int u,int k){
    two ret={0,0};
    if (!u) return ret;
    int lsize=T[T[u].ls].size+1;
    if (k>=lsize){
        ret=split(T[u].rs,k-lsize);
        T[u].rs=ret.ls;
        ret.ls=u;
    }
    else{
        ret=split(T[u].ls,k);
        T[u].ls=ret.rs;
        ret.rs=u;
    }
    update(u);
    return ret;
}
inline int merge(int x,int y){
    if (!x) return y;
    if (!y) return x;
    if (T[x].heap<T[y].heap){
        T[x].rs=merge(T[x].rs,y);
        update(x);
        return x;
    }
    else{
        T[y].ls=merge(x,T[y].ls);
        update(y);
        return y;
    }
}
inline void insert(int pos,int x){
    cnt++;
    T[cnt].size=1,T[cnt].val=x,T[cnt].hash=x;
    T[cnt].heap=rand();
    two p1=split(root,pos);
    root=merge(p1.ls,merge(cnt,p1.rs));
}
inline int query(int l,int r){
    //printf("%d %d ",l,r);
    two p1=split(root,r);
    two p2=split(p1.ls,l-1);
    unsigned int ret=T[p2.rs].hash;
    root=merge(merge(p2.ls,p2.rs),p1.rs);
    //printf("%u\n",ret);
    return ret;
}
inline void bl(int u){
//    printf("%d %d %u\n",u,T[u].size,T[u].hash);
    if (T[u].ls) bl(T[u].ls);
    if (T[u].rs) bl(T[u].rs);
} 
int main(){
    mi[0]=1;
    for (int i=1;i<=100000;i++) mi[i]=mi[i-1]*base;
    scanf("%s",c+1);
    len=strlen(c+1);
    for (int i=1;i<=len;i++){
        insert(i-1,c[i]-'a'+1);
    } 
    bl(root);
    read(n);
    while (n--){
        scanf("%s",op);
        if (op[0]=='Q'){
            read(x),read(y);
            if (x<y) swap(x,y);
            int l=1,r=cnt-x+1,ans=0;
            while (l<=r){
                int mid=l+r>>1;
                if (query(x,x+mid-1)==query(y,y+mid-1)) ans=mid,l=mid+1;
                else r=mid-1;
            }
            printf("%d\n",ans);
        }
        if (op[0]=='R'){
            read(x); scanf("%s",a);
            two p1=split(root,x-1);
            two p2=split(p1.rs,1);
            T[p2.ls].hash=T[p2.ls].val=a[0]-'a'+1;
            root=merge(p1.ls,merge(p2.ls,p2.rs));
        }
        if (op[0]=='I'){
            read(x); scanf("%s",a);
            insert(x,a[0]-'a'+1);
        }
    }
    return 0;
}