「BZOJ2434」[NOI2011]阿狸的打字机

Description

阿狸喜欢收藏各种稀奇古怪的东西,最近他淘到一台老式的打字机。打字机上只有 2828 个按键,分别印有 2626 个小写英文字母和 B 、 P 两个字母。 经阿狸研究发现,这个打字机是这样工作的:

  • 输入小写字母,打字机的一个凹槽中会加入这个字母(按 P 前凹槽中至少有一个字母)。
  • 按一下印有 B 的按键,打字机凹槽中最后一个字母会消失。
  • 按一下印有 P 的按键,打字机会在纸上打印出凹槽中现有的所有字母并换行,但凹槽中的字母不会消失(保证凹槽中至少有一个字母)。

例如,阿狸输入 aPaPBbP ,纸上被打印的字符如下:

1
2
3
a 
aa
ab

我们把纸上打印出来的字符串从 11 开始顺序编号,一直到 nn 。打字机有一个非常有趣的功能,在打字机中暗藏一个带数字的小键盘,在小键盘上输入两个数 (x,y)(x,y) (其中 1x,yn1 \le x,y \le n ),打字机会显示第 xx 个打印的字符串在第 yy 个打印的字符串中出现了多少次。
阿狸发现了这个功能以后很兴奋,他想写个程序完成同样的功能,你能帮助他么?

Input

输入的第一行包含一个字符串,按阿狸的输入顺序给出所有阿狸输入的字符。
第二行包含一个整数 mm ,表示询问个数。 接下来 mm 行描述所有由小键盘输入的询问。其中第i行包含两个整数 x,yx, y ,表示第i个询问为 (x,y)(x, y)

Output

输出 mm 行,其中第 ii 行包含一个整数,表示第 ii 个询问的答案。

Sample Input

1
2
3
4
5
aPaPBbP 
3
1 2
1 3
2 3

Sample Output

1
3

HINT

所有测试数据的范围和特点如下表所示:

测试点编号 nn 的规模 mm 的规模 字符串长度 输入总长 (输入文件第一行的字符数)
1 1n1001\le n \le 100 1m10001\le m \le 1000 - 100\le 100
2 1n1001\le n \le 100 1m10001\le m \le 1000 - 100\le 100
3 1n10001\le n \le 1000 1m1041\le m \le 10^4 单个长度 1000\le 1000 ,总长度 105\le 10^5 105\le 10^5
4 1n10001\le n \le 1000 1m1041\le m \le 10^4 单个长度 1000\le 1000 ,总长度 105\le 10^5 105\le 10^5
5 1n1041\le n \le 10^4 1m1051\le m \le 10^5 总长度 105\le 10^5 105\le 10^5
6 1n1041\le n \le 10^4 1m1051\le m \le 10^5 总长度 105\le 10^5 105\le 10^5
7 1n1041\le n \le 10^4 1m1051\le m \le 10^5 总长度 105\le 10^5 105\le 10^5
8 1n1051\le n \le 10^5 1m1051\le m \le 10^5 - 105\le 10^5
9 1n1051\le n \le 10^5 1m1051\le m \le 10^5 - 105\le 10^5
10 1n1051\le n \le 10^5 1m1051\le m \le 10^5 - 105\le 10^5

Solution

force

对于每一个询问按照yy排序一遍,然后相同的yy用同义词遍历的solve得到的sumsum数组统计答案即可。

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
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<map>
#include<bitset>
#include<queue>
#define mk make_pair
#define fi first
#define nd second
#define pii pair<int,int>
#define pb push_back
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
inline ll read() {ll x = 0; char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}
const int N = 1e6;

char s[N];
int n;
int ch[N][26], tot, fa[N], pos[N];
int cnt[N], m;
vector<int> v[N];
int fail[N];
void getfail() {
queue<int>q;
for(int i = 0; i < 26; ++i) if(ch[0][i]) q.push(ch[0][i]);
while(!q.empty()) {
int x = q.front(); q.pop();
for(int i = 0; i < 26; ++i) {
if(ch[x][i]) {
fail[ch[x][i]] = ch[fail[x]][i];
q.push(ch[x][i]);
}
else ch[x][i] = ch[fail[x]][i];
}
}
}
struct TT {
int x, y, i;
}t[N];
bool cmp(TT _x, TT _y) {
return _x.y < _y.y;
}
int sum[N], st[N], top, ans[N];
bool vis[N];
void solve(int x) {
x = pos[x];
while(x) {
for(int j = x; j; j = fail[j]) for(int k = 0; k < v[j].size(); ++k) {
++sum[v[j][k]];
if(!vis[v[j][k]]) {
vis[v[j][k]] = 1;
st[++top] = v[j][k];
}
}
x = fa[x];
}
}
int main() {
int now = 0;
scanf("%s",s + 1);
n = strlen(s + 1);
for(int i = 1; i <= n; ++i) {
if(s[i] >= 'a' && s[i] <= 'z') {
int to = s[i] - 'a';
if(!ch[now][to]) ch[now][to] = ++tot, fa[tot] = now;
now = ch[now][to];
}
if(s[i] == 'B') now = fa[now];
if(s[i] == 'P')
v[now].pb(++m), pos[m] = now;
}
getfail();
int Q = read();
for(int i = 1; i <= Q; ++i)
t[i].x= read(), t[i].y = read(), t[i].i= i;
sort(t +1, t +1 +Q, cmp);
for(int i = 1, j; i <= Q; i = j) {
j = i;
solve(t[i].y);
while(t[j].y == t[i].y) {
ans[t[j].i] = sum[t[j].x];
++j;
}
while(top) {
vis[st[top]] = 0;
sum[st[top--]] = 0;
}
}
for(int i = 1; i <= Q; ++i)
writeln(ans[i]);
return 0;
}

std

对于询问(x,y)(x,y),求xxyy里出现过几次,相当于在原来trietrie树上跑yy这条链,然后跑链上的每一个节点的failfail来统计答案。实际上就是枚举yy的前缀,然后找前缀的后缀就是找xx了。
换一句话说对于一个循环(x,y)(x,y)就是要从xx出发经过failfail边一共可以到达多少个yy链上的点。
我们可以模拟一遍dfsdfs很显然当前到达的节点即00到其路径的链,所以直接用树状数组查询即可。

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
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<map>
#include<bitset>
#include<queue>
#define mk make_pair
#define fi first
#define nd second
#define pii pair<int,int>
#define pb push_back
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
inline ll read() {ll x = 0; char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}
const int N = 1e6;

char s[N];
int n;
int ch[N][26], tot, fa[N], pos[N], CH[N][26];
int cnt[N], m;
vector<int> v[N];
int fail[N];
void getfail() {
queue<int>q;
for(int i = 0; i < 26; ++i) if(ch[0][i]) q.push(ch[0][i]);
while(!q.empty()) {
int x = q.front(); q.pop();
for(int i = 0; i < 26; ++i) {
if(ch[x][i]) {
fail[ch[x][i]] = ch[fail[x]][i];
q.push(ch[x][i]);
}
else ch[x][i] = ch[fail[x]][i];
}
}
}
struct TT {
int x, y, i;
}t[N];
bool cmp(TT _x, TT _y) {
return _x.y < _y.y;
}
struct Edge {
int u, v, nxt;
}e[N * 2];
int head[N], en;
void addedge(int x, int y) {
e[++en].u = x, e[en].v = y,e[en].nxt = head[x], head[x] = en;
}
int L[N], R[N], num;
void DFS(int x) {
L[x] = ++num;
for(int i = head[x]; i;i =e[i].nxt) DFS(e[i].v);
R[x] = num;
}
int c[N];
void add(int x, int v) {
for(; x <= num; x += x & -x)
c[x] += v;
}
int query(int x) {
int res = 0;
for(; x; x -= x & -x)
res += c[x];
return res;
}
int ans[N];
int ql[N], qr[N];
void solve(int x) {
add(L[x], 1);
if(ql[x]) {
for(int i = ql[x]; i <= qr[x]; ++i) {
ans[t[i].i] = query(R[t[i].x]) - query(L[t[i].x] - 1);
}
}
for(int i = 0; i < 26; ++i)
if(CH[x][i]) solve(CH[x][i]);
add(L[x], -1);
}
int main() {
int now = 0;
scanf("%s",s + 1);
n = strlen(s + 1);
for(int i = 1; i <= n; ++i) {
if(s[i] >= 'a' && s[i] <= 'z') {
int to = s[i] - 'a';
if(!ch[now][to]) ch[now][to] = ++tot, fa[tot] = now;
now = ch[now][to];
}
if(s[i] == 'B') now = fa[now];
if(s[i] == 'P')
v[now].pb(++m), pos[m] = now;
}
for(int i = 0; i <= tot; ++i) memmove(CH[i], ch[i], sizeof ch[i]);
getfail();
for(int i = 1; i <= tot; ++i) addedge(fail[i], i);
DFS(0);
int Q = read();
for(int i = 1; i <= Q; ++i)
t[i].x= read(), t[i].y = read(), t[i].i= i;
sort(t +1, t +1 +Q, cmp);
for(int i = 1; i <= Q; ++i) {
t[i].x = pos[t[i].x];
t[i].y = pos[t[i].y];
}
for(int i = 1, j; i <= Q; i = j) {
j = i;
ql[t[i].y] = i;
while(t[j].y== t[i].y) ++j;
qr[t[i].y] = j - 1;
}
solve(0);
for(int i = 1; i <= Q; ++i)
writeln(ans[i]);
return 0;
}