隐藏
「bzoj省队十连测Day2 C」幻想 - 后缀平衡树 | Bill Yang's Blog
0%

「bzoj省队十连测Day2 C」幻想 - 后缀平衡树

题目大意

    我们伟大的领袖V成功地找到了自己被赋予力量的意义——既然有如此强大的能力,就应该去守护人们的幻想。
    一个人的幻想是一个字符串,幻想是在不断变化的,所以可能会在末尾加上一个字符或者删去一个字符。为了守护幻想,V需要知道在字符串中第$L$个字符(字符由$1$开始编号)到第$R$个的串中存在多少个V给定的串。


题目分析

看操作就是后缀平衡树的题。
询问包含的串个数可以在平衡树上二分比较后缀,通过前缀和相减的形式算出包含的串数。
例,查询$abcd$出现次数,即查询比$abcd(53)$小的后缀个数$-$比$abcd(-2)$小的后缀个数。

需要注意的是,原本后缀平衡树需要将串反过来,但在本题中将串反过来就不好编号了。
因此不将串反过来,编号映射的时候改一下即可。


代码

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
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;

#define double long double

inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}

const int maxn=200005,maxq=5000005;

mt19937 g(rand());

struct Tree {
int child[2];
int val,d;
double num;
vector<int> vec;
};

int qlen,qs[maxq],a[maxn];

struct Treap {
Tree tree[maxn];
int size,root;
#define d(x) tree[x].d
#define ls(x) tree[x].child[0]
#define rs(x) tree[x].child[1]
#define val(x) tree[x].val
#define num(x) tree[x].num
#define mid (l+r)/2
int newnode(int val) {
int now=++size;
val(now)=val;
d(now)=g()%maxn;
num(now)=ls(now)=rs(now)=0;
return now;
}
void rebuild(int &index,double l,double r) { //重新计算映射
if(!index)return;
num(index)=mid;
rebuild(ls(index),l,mid);
rebuild(rs(index),mid,r);
}
void push_up(int index) { //vector归并
int ls=ls(index),rs=rs(index);
tree[index].vec.clear(),tree[index].vec.resize(tree[ls].vec.size()+tree[rs].vec.size());
merge(tree[ls].vec.begin(),tree[ls].vec.end(),tree[rs].vec.begin(),tree[rs].vec.end(),tree[index].vec.begin());
auto it=tree[index].vec.begin();
for(; it!=tree[index].vec.end(); it++)if(*it>index)break;
tree[index].vec.insert(it,index);
}
void rotate(int &index,bool side,double l,double r) {
int son=tree[index].child[side^1];
tree[index].child[side^1]=tree[son].child[side];
tree[son].child[side]=index;
tree[son].vec=tree[index].vec;
push_up(index);
index=son;
rebuild(index,l,r);
}
int cmp(int x,int y) {
return val(x)>val(y)||(val(x)==val(y)&&num(x-1)>=num(y-1));
}
void insert(int &index,double l,double r,int New) {
if(!index) {
index=New;
num(index)=mid;
tree[index].vec.push_back(New);
return;
}
tree[index].vec.push_back(New);
bool side=cmp(New,index);
int &son=tree[index].child[side];
if(side==0)insert(son,l,mid,New);
else insert(son,mid,r,New);
if(d(index)<d(son))rotate(index,side^1,l,r);
}
void insert(int val) {
int New=newnode(val);
insert(root,0,1e18,New);
}
void del(int &index,double l,double r) {
if(!ls(index)&&!rs(index)) {
tree[index].vec.clear();
index=0;
size--;
return;
}
bool side=d(rs(index))<d(ls(index));
rotate(index,side,l,r);
tree[index].vec.pop_back();
if(side==0)del(ls(index),l,mid);
else del(rs(index),mid,r);
}
void find_del(int &index,double l,double r) {
if(index==size) {
del(index,l,r);
return;
}
tree[index].vec.pop_back();
bool side=!(ls(index)&&tree[ls(index)].vec.back()==size);
if(side==0)find_del(ls(index),l,mid);
else find_del(rs(index),mid,r);
}
int ask(int index,int l,int r) {
if(!index)return 0;
return upper_bound(tree[index].vec.begin(),tree[index].vec.end(),r)-lower_bound(tree[index].vec.begin(),tree[index].vec.end(),l);
}
int query(int index,int Left,int Right) {
if(!index||Left>Right)return 0;
bool side=0;
for(int i=1; i<=min(qlen,index+1); i++)
if(qs[i]!=a[index-i+1]) {
side=a[index-i+1]<qs[i];
break;
}
if(!side)return query(ls(index),Left,Right);
return (Left<=index&&index<=Right)+ask(ls(index),Left,Right)+query(rs(index),Left,Right);
}
} treap;

int trans(char x) {
return islower(x)?x-'a':x-'A'+26;
}

int q,len,lastans=0;
char s[maxq],s2[maxq];

void Decode() {
qlen=strlen(s2+1);
for(int i=1; i<=qlen; i++)qs[i]=(trans(s2[i])+lastans)%52;
reverse(qs+1,qs+qlen+1);
}

int main() {
srand(99995999);
scanf("%s",s+1);
len=strlen(s+1);
for(int i=1; i<=len; i++)treap.insert(a[i]=trans(s[i]));
a[0]=treap.tree[0].d=-1;
q=Get_Int();
for(int i=1; i<=q; i++) {
int opt=Get_Int();
if(opt==1) {
char x=' ';
while(!isalpha(x))x=getchar();
treap.insert(a[++len]=(trans(x)+lastans)%52);
} else if(opt==2) {
treap.find_del(treap.root,0,1e18);
len--;
} else {
int x=Get_Int()^lastans,y=Get_Int()^lastans;
scanf("%s",s2+1);
Decode();
qs[++qlen]=-2,lastans=-treap.query(treap.root,x+qlen-2,y);
qs[qlen]=53,lastans+=treap.query(treap.root,x+qlen-2,y);
printf("%d\n",lastans);
}
}
return 0;
}
姥爷们赏瓶冰阔落吧~