BZOJ - 1014 火星人prefix(Splay+二分+Hash)

Posted on | In , ,

思路

对于无修改的LCP，常用的算法是后缀数组/二分+Hash。但当场景转换为带修改的LCP查询时，后缀数组就无能为力了，因为这样每次都要重建一次后缀数组才能知道LCP的值。但对于二分+Hash来说，我们只要能够知道一段字符串的hash即可，而Hash值显然是可以用Splay维护的，同时Splay也同时支持插入和修改操作。对于题目要求的三种操作，我们这样实现：

  1. 查询操作：二分长度，令两个位置为x,y。我们查找排行为x-1和x+len的两个节点，令其为pre和nxt。将pre splay到根(pre->splay())，nxt splay到pre的儿子(nxt->splay(pre))。那么nxt的左儿子就是我们需要的区间。由于旋转操作时维护了Hash值，所以我们直接取该节点上维护的Hash值就是这段区间的Hash值。对于y的Hash值同理，然后比较Hash值就能判断两个字符串是否相等。
  2. 插入操作：查找排行为x和x+1的两个节点，x splay到根，x+1 splay到x的儿子，对x+1的左儿子直接插入即可
  3. 修改操作：找到排行为x的节点直接修改

需要注意的是由于使用Splay时我们通常会插入头尾两个辅助节点，我们maintain Hash值的时候不能把这两个值算上。

代码

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
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define INTINF 0x7fffffff
#define LLINF 0x7fffffffffffffff
#define ms(a,val) memset((a),(val),(sizeof(a)))
#define sqr(x) ((x)*(x))
#define all(x) (x).begin(),(x).end()
using namespace std;
ll quickpow(ll a,ll b,ll MOD){ll ans=1;a%=MOD;while(b){if(b&1ll)ans=ans*a%MOD;a=a*a%MOD,b>>=1;}return ans;}
ll gcd(ll a,ll b){return a%b==0?b:gcd(b,a%b);}
//head

const int MAXN=150005;
char str[MAXN];
ull num[MAXN];
ull seed[MAXN];
void init(){
    seed[0]=1;
    for(int i=1;i<MAXN;i++)seed[i]=seed[i-1]*27;
}
template <typename T>
struct memoryPool{
    T buf[MAXN],*tail,*ret[MAXN];
    int top;
    void init(){
        tail=buf,top=0;
    }
    T* newnode(){
        return top?ret[--top]:tail++;
    }
    void retnode(T *rub){
        ret[top++]=rub;
    }
};
struct SplayTree{
    struct node{
        node *child[2],*parent,**root;
        int sizes,tsz,useful;
        //tags
        ull val,hashs;
        node(){
            child[0]=child[1]=NULL,parent=NULL;
            sizes=1,tsz=1,hashs=0,useful=1,val=0;
        }
        node(node *parent,node **root,ull val):parent(parent),root(root),val(val){
            child[0]=child[1]=NULL,sizes=1,tsz=1,hashs=val,useful=1;
        }
        int relation(){
            return parent->child[0]==this?0:1;
        }
        void maintain(){
            sizes=1,hashs=val,tsz=useful?1:0;
            if(child[0]){
                sizes+=child[0]->sizes,tsz+=child[0]->tsz;
                if(child[0]->useful){
                    if(useful)hashs=child[0]->hashs*27+hashs;
                    else hashs=child[0]->hashs;
                }
                else{
                    hashs=child[0]->hashs*27+hashs;
                }
            }
            if(child[1]){
                sizes+=child[1]->sizes,tsz+=child[1]->tsz;
                if(child[1]->useful){
                    hashs=hashs*seed[child[1]->sizes]+child[1]->hashs;
                }
                else{
                    hashs=hashs*seed[child[1]->tsz]+child[1]->hashs;
                }
            }
        }
        void rotates(){
            int x=relation();
            node *oldparent=parent;
            if(oldparent->parent)oldparent->parent->child[oldparent->relation()]=this;
            parent=oldparent->parent,oldparent->child[x]=child[x^1];
            if(child[x^1])child[x^1]->parent=oldparent;
            child[x^1]=oldparent,oldparent->parent=this,oldparent->maintain(),maintain();
            if(!parent)*root=this;
        }
        void splay(node *target=NULL){
            while(parent!=target){
                if(parent->parent==target)rotates();
                else if(parent->relation()==relation())parent->rotates(),rotates();
                else rotates(),rotates();
            }
        }
        int ranks(){
            return !child[0]?0:child[0]->sizes;
        }
    }*root;
    memoryPool<node> mp;
    void init(){
        mp.init(),root=NULL;
    }
    void clr(node *v){
        if(v->child[0])clr(v->child[0]);
        if(v->child[1])clr(v->child[1]);
        mp.retnode(v);
    }
    //shouldn't splay for selecting segment
    node* findByRank(int k){
        node *v=root;
        while(k!=v->ranks()){
            if(k<v->ranks())v=v->child[0];
            else k-=v->ranks()+1,v=v->child[1];
        }
        return v;
    }
    void inserts(ull val,int pos){
        node *pre=findByRank(pos);
        pre->splay();
        node *nxt=findByRank(pos+1);
        nxt->splay(pre);
        node *v=mp.newnode();
        v->child[0]=v->child[1]=NULL;
        v->parent=nxt,v->val=val,v->hashs=val,v->root=&root,v->useful=1,v->sizes=1,v->tsz=1;
        nxt->child[0]=v;
        nxt->maintain(),pre->maintain();
    }
    void modify(ull val,int pos){
        node *v=findByRank(pos);
        v->splay();
        v->val=val;
        v->maintain();
    }
    node* build(int l,int r,int tl,int tr,node *parent){
        int mid=(l+r+1)>>1;
        node *v=mp.newnode();
        v->parent=parent,v->val=v->hashs=num[mid],v->root=&root;
        v->child[0]=v->child[1]=NULL,v->sizes=1;
        if(mid==tl||mid==tr)v->useful=0;
        else v->useful=1;
        v->tsz=v->useful;
        if(l<mid)v->child[0]=build(l,mid-1,tl,tr,v);
        if(r>mid)v->child[1]=build(mid+1,r,tl,tr,v);
        v->maintain();
        return v;
    }
    bool judge(int x,int y,int len){
        ull hashx=0,hashy=0;
        if(!len)return true;
        node *pre=findByRank(x-1);
        pre->splay();
        node *nxt=findByRank(x+len);
        nxt->splay(pre);
        hashx=nxt->child[0]->hashs;
        pre=findByRank(y-1);
        pre->splay();
        nxt=findByRank(y+len);
        nxt->splay(pre);
        hashy=nxt->child[0]->hashs;
        return hashx==hashy;
    }
}Splay;
char cmd[5];

int main(){
    #ifndef ONLINE_JUDGE
    freopen("input.in","r",stdin);
    freopen("output.out","w",stdout);
    #endif // ONLINE_JUDGE
    init();
    while(gets(str)){
        Splay.init();
        int q,len=strlen(str),temp,x,y;
        num[0]=0,num[len+1]=0;
        for(int i=0;i<len;i++)num[i+1]=str[i]-'a'+1;
        Splay.root=Splay.build(0,len+1,0,len+1,NULL);
        scanf("%d",&q);
        for(int z=0;z<q;z++){
            scanf("%s",cmd);
            if(cmd[0]=='Q'){
                scanf("%d%d",&x,&y);
                int lb=0,ub=len-max(x,y)+1;
                while(lb<ub){
                    int mid=(lb+ub+1)>>1;
                    if(Splay.judge(x,y,mid))lb=mid;
                    else ub=mid-1;
                }
                printf("%d\n",lb);
            }
            else if(cmd[0]=='R'){
                scanf("%d%s",&temp,cmd);
                Splay.modify((ull)(cmd[0]-'a'+1),temp);
            }
            else if(cmd[0]=='I'){
                scanf("%d%s",&temp,cmd);
                Splay.inserts((ull)(cmd[0]-'a'+1),temp);
                len++;
            }
        }
        getchar();
        Splay.clr(Splay.root);
    }
    return 0;
}