摘要:平衡树维护区间hash

[JSOI2008]火星人

题面

题目分析

如何比较两个字符串相等,首先是想到用hash.

所以说要求lcp,只要二分出一个长度,用数据结构取出区间的hash值比较即可.

考虑维护一个数据结构,支持插入节点,维护区间的hash.

使用splay,将原序列对应在树上.

一个区间生成的hash值相当于一个以区间长度为度的多项式的值,根据splay作为区间树性质,一个节点的左子树在序列上都在它的前面,右子树都在它的后面,所以说在合并这个节点的信息时,仅考虑当前节点代表的子树,这个点生成的hash中它这一项应该乘上的base即为左子树的大小,左子树已经处理好的hash值就直接加上,右子树因为考虑上了左子树,要全体乘上左子树大小+1(即加上当前节点),因为乘法分配律所以直接乘上这个右子树处理出的hash的和即可.

取模好像很麻烦,直接用unsigned long long自然溢出即可,查询的时候旋转出对应区间,取这个区间对应的子树的根的hash值就是维护出的hash值了.

对于插入操作,假设要在序列的位置$k$之后进行操作,根据区间树的性质,树上排名为$k$的点对应在序列的位置$k$上,我们找到排名为$k$的节点$p$和排名为$k+1$的节点$q$,将$p$旋至根,$q$旋至$p$的儿子,这时候$q$的左儿子为空,在左儿子上新建需要插入的节点即可.

代码

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
#include "iostream"
#include "cstdlib"
#include "cstdio"
#include "cstring"
#include "cmath"
#include "cctype"
#include "ctime"
#include "iomanip"
#include "algorithm"
#include "set"
#include "queue"
#include "map"
#include "stack"
#include "deque"
#include "vector"
#define R register
#define INF 0x3f3f3f3f
#define debug(x) printf("debug:%lld\n",x)
#define debugi(x) printf("debug:%d\n",x)
#define debugf(x) printf("debug:%llf\n",x)
#define endl putchar('\n')
typedef long long lxl;
typedef unsigned long long ulxl;
const lxl big=200010,mod=233;
lxl m,len,root,NodeCnt;
char s[big];
lxl c[2][big],base[big],fa[big],a[big];
ulxl hash[big],size[big],val[big];
inline lxl read()
{
char c(getchar());
lxl f(1),x(0);
for(;!isdigit(c);(c=='-')&&(f=-1),c=getchar());
for(;isdigit(c);x=(x<<1)+(x<<3)+(c^48),c=getchar());
return f*x;
}
#define lson c[0][t]
#define rson c[1][t]
inline void PushUp(lxl t)
{
ulxl tmp=base[size[lson]]*val[t];
hash[t]=hash[lson]+hash[rson]*base[size[lson]+1]+tmp;
size[t]=size[lson]+size[rson]+1;
}
inline void rotate(lxl x)
{
lxl y=fa[x],z=fa[y],d=c[1][y]==x;
if(c[1][z]==y)c[1][z]=x;else c[0][z]=x;
fa[x]=z,fa[y]=x,fa[c[d^1][x]]=y;
c[d][y]=c[d^1][x],c[d^1][x]=y;
PushUp(y),PushUp(x);
}
inline void splay(lxl x,lxl goal)
{
while(fa[x]!=goal)
{
lxl y=fa[x],z=fa[y];
if(fa[y]!=goal)rotate((c[0][y]==x)^(c[0][z]==y)?x:y);
rotate(x);
}
if(!goal)root=x;
}
void BuildTree(lxl &t,lxl l,lxl r,lxl from)
{
if(l>r)return;
lxl mid((l+r)>>1);
if(!t)t=++NodeCnt;
fa[t]=from,hash[t]=val[t]=a[mid],size[t]=1;
BuildTree(lson,l,mid-1,t),BuildTree(rson,mid+1,r,t);
PushUp(t);
}
lxl find(lxl t,lxl k)
{
if(size[lson]+1==k)return t;
if(size[lson]>=k)return find(lson,k);
else return find(rson,k-1-size[lson]);
}
inline void insert(lxl k,ulxl d)
{
lxl pos1=find(root,k),pos2=find(root,k+1),t=++NodeCnt;
splay(pos1,0),splay(pos2,pos1);
c[0][pos2]=t,fa[t]=pos2;
hash[t]=val[t]=d,size[t]=1;
PushUp(pos2),splay(t,0);
}
inline ulxl spilt(lxl l,lxl r)
{
lxl x=find(root,l-1),y=find(root,r+1);
splay(x,0),splay(y,x);
return hash[c[0][y]];
}
inline void modify(lxl x,ulxl d)
{
lxl pos=find(root,x);
splay(pos,0);
val[pos]=d,PushUp(pos);
}
inline bool check(lxl x,lxl y,lxl lim)
{
lxl l=x,r=x+lim-1;
ulxl val1,val2;
val1=spilt(l,r);
l=y,r=y+lim-1;
val2=spilt(l,r);
return val1==val2;
}
inline void query(lxl x,lxl y)
{
lxl l(1),r(NodeCnt-y),mid,ans=-1;
while(l<=r)
{
mid=(l+r)>>1;
if(check(x,y,mid))ans=mid,l=mid+1;
else r=mid-1;
}
if(!(~ans))printf("0\n");
else printf("%lld\n",ans);
}
inline void prework()
{
base[0]=1;
for(R int i(1);i<big;++i)base[i]=base[i-1]*mod;
}
int main(void)
{
// freopen("data.txt","r",stdin);
prework();
scanf("%s",s+1);
len=strlen(s+1);
for(R int i(1);i<=len;++i)a[i+1]=s[i]-'a'+1;
BuildTree(root,1,len+2,0);
m=read();
for(R int i(1);i<=m;++i)
{
char opt[50];scanf("%s",opt+1);
if(opt[1]=='Q')
{
lxl x=read()+1,y=read()+1;
if(x>y)std::swap(x,y);
query(x,y);
}
else if(opt[1]=='R')
{
ulxl x=read()+1,d;
char ch;scanf("%c",&ch);
d=ch-'a'+1;
modify(x,d);
}
else
{
ulxl x=read()+1,d;
char ch;scanf("%c",&ch);
d=ch-'a'+1;
insert(x,d);
}
}
return 0;
}