Description
阿狸喜欢收藏各种稀奇古怪的东西，最近他淘到一台老式的打字机。打字机上只有28个按键，分别印有26个小写英文字母和’B’、‘P’两个字母。
经阿狸研究发现，这个打字机是这样工作的：
输入小写字母，打字机的一个凹槽中会加入这个字母(这个字母加在凹槽的最后)。
按一下印有’B’的按键，打字机凹槽中最后一个字母会消失。
按一下印有’P’的按键，打字机会在纸上打印出凹槽中现有的所有字母并换行，但凹槽中的字母不会消失。
例如，阿狸输入aPaPBbP，纸上被打印的字符如下：
a
aa
ab
我们把纸上打印出来的字符串从1开始顺序编号，一直到n。打字机有一个非常有趣的功能，在打字机中暗藏一个带数字的小键盘，在小键盘上输入两个数(x,y)（其中1≤x,y≤n），打字机会显示第x个打印的字符串在第y个打印的字符串中出现了多少次。
阿狸发现了这个功能以后很兴奋，他想写个程序完成同样的功能，你能帮助他么？
输入的第一行包含一个字符串，按阿狸的输入顺序给出所有阿狸输入的字符。
第二行包含一个整数m，表示询问个数。
接下来m行描述所有由小键盘输入的询问。其中第i行包含两个整数x, y，表示第i个询问为(x, y)。
Output
输出m行，其中第i行包含一个整数，表示第i个询问的答案。
aPaPBbP
3
1 2
1 3
2 3
Sample Output
2
1
0
HINT
1<=N<=10^5
1<=M<=10^5
输入总长<=10^5
Solution
AC自动机+树状数组。
刚拿到这道题真的一头雾水。。只会建Trie暴力AC自动机匹配。。其实我们可以想，答案是在干什么？
统计x字符串在y字符串中出现的次数。x在y中出现当且仅当x是y的一个前缀的一个后缀。
首先要明确两点：
一、对于y的所有前缀，就是Trie树上根到y节点的路径：
如图所示，“hers ”的所有前缀为h,he,her,hers,都在root到最右边绿色节点的路径上。
二、对于一个节点i，i的所有出现过的后缀其实是fail树中root到i点的路径，如图：
hers(9)的一个后缀s(3)恰好为其fail树中的父节点。
有了这两点我们可以得到一个比较朴素的暴力，对于每次询问，枚举y字符串的所有前缀，在fail树中统计x节点是多少个这些前缀中的祖先（自己也算自己的祖先）。（可能有点绕，大家慢慢捋一捋）
例如询问hers中出现过多少个he，就是he代表的节点2在hers的前缀{0,1,2,8,9}中成为祖先的次数，即1次。因此hers中he出现了1次。
因为题目没有强制在线，因此我们可以离线处理所有询问。
我们可以对这颗Trie进行dfs，这样每当访问到一个节点y的时候，root到y的路径上的所有点已经访问过了。假设有一个询问(x,y)，那么答案就是fail树中，root到y这些节点在x的子树中出现次数。
为什么呢？因为从x的子树中一定可以走到x，也就是说x一定是其子树中所有节点的后缀。
统计x的子树中出现次数，我们可以先对fail树进行另一遍dfs，把子树变成序列，然后答案就是某一段序列（x的子树序列）中有多少个root到y的节点。
于是问题就变成了点修改（dfs中遍历到y时+1，y出栈时-1），区间求和（另一遍dfs中x子树代表的区间）的问题，可以用树状数组搞定。
Code
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 <queue>
using namespace std;
typedef long long LL;
const int INF = 1009999999;
const int maxn = 100005;
int getint() {
int r = 0, k = 1; char c = getchar();
for (; '0' > c || c > '9'; c = getchar()) if (c == '-') k = -1;
for (; '0' <= c && c <= '9'; c = getchar()) r = r * 10 - '0' + c;
return r * k;
}
queue<int> Q;
char str[maxn], tmp[maxn];
int tid[maxn], dfn[maxn], clo;
struct query_type { int to, next, id; } edge[maxn];
int h[maxn], cnte = 1;
inline int lowbit(int x) { return x & (-x); }
namespace Trie {
int go[maxn][26], fa[maxn], fail[maxn], root = 0, tot, trans[maxn][26];
struct edge_type { int to, next; } edge[maxn];
int h[maxn], cnte = 1;
void ins(int x, int y) {
edge[++cnte].to = y;
edge[cnte].next = h[x];
h[x] = cnte;
}
void build_fail() {
for (int i = 0; i < 26; ++i)
if (go[root][i]) {
fail[go[root][i]] = root;
Q.push(go[root][i]);
}
int now;
while (!Q.empty()) {
now = Q.front(); Q.pop();
for (int i = 0; i < 26; ++i) {
if (go[now][i]) {
Q.push(go[now][i]);
fail[go[now][i]] = go[fail[now]][i];
} else go[now][i] = go[fail[now]][i];
}
}
}
void dfs(int now, int father) {
tid[now] = ++clo;
for (int i = h[now]; i; i = edge[i].next)
if (edge[i].to != father)
dfs(edge[i].to, now);
dfn[now] = clo;
}
void dfs_fail() {
for (int i = 1; i <= tot; ++i)
ins(fail[i], i);
dfs(root, -1);
}
}
using Trie::go;
using Trie::fa;
using Trie::tot;
using Trie::trans;
inline bool is_lower(char x) { return 'a' <= x && x <= 'z'; }
int nod[maxn], cnt, Ans[maxn];
void init() {
scanf("%s", str);
int now = Trie::root;
for (int i = 0; str[i]; ++i) {
if (is_lower(str[i])) {
if (!go[now][str[i]-'a']) {
trans[now][str[i]-'a'] = go[now][str[i]-'a'] = ++tot;
fa[tot] = now;
}
now = go[now][str[i]-'a'];
} else {
if (str[i] == 'B') now = fa[now];
else nod[++cnt] = now;
}
}
Trie::build_fail();
Trie::dfs_fail();
}
void ins(int x, int y, int z) {
edge[++cnte].to = y;
edge[cnte].next = h[x];
edge[cnte].id = z;
h[x] = cnte;
}
int c[maxn];
void Add(int pos, int val) {
for (int i = pos; i <= clo; i += lowbit(i))
c[i] += val;
}
int query(int pos) {
int ret = 0;
for (int i = pos; i; i -= lowbit(i))
ret += c[i];
return ret;
}
inline int Query(int l, int r) { return query(r) - query(l - 1); }
void dfs(int now, int father) {
Add(tid[now], 1);
for (int i = h[now]; i; i = edge[i].next)
Ans[edge[i].id] = Query(tid[edge[i].to], dfn[edge[i].to]);
for (int i = 0; i < 26; ++i)
if (trans[now][i])
dfs(trans[now][i], now);
Add(tid[now], -1);
}
int main() {
init();
int m = getint(), x, y;
for (int i = 1; i <= m; ++i) {
x = getint(); y = getint();
ins(nod[y], nod[x], i);
}
dfs(Trie::root, -1);
for (int i = 1; i <= m; ++i)
printf("%d\n", Ans[i]);
return 0;
}
|