Blackops

初心易得，始终难守

0%

BZOJ 2434 阿狸的打字机（AC自动机构造fail树+DFS序+离线树状数组）

发表于 分类于 ， ，

2434: [Noi2011]阿狸的打字机

Time Limit: 10 Sec Memory Limit: 256 MB
Submit: 3491 Solved: 1907
Description

阿狸喜欢收藏各种稀奇古怪的东西，最近他淘到一台老式的打字机。打字机上只有28个按键，分别印有26个小写英文字母和’B’、’P’两个字母。

经阿狸研究发现，这个打字机是这样工作的：

| 输入小写字母，打字机的一个凹槽中会加入这个字母(这个字母加在凹槽的最后)。

| 按一下印有’B’的按键，打字机凹槽中最后一个字母会消失。

| 按一下印有’P’的按键，打字机会在纸上打印出凹槽中现有的所有字母并换行，但凹槽中的字母不会消失。
例如，阿狸输入aPaPBbP，纸上被打印的字符如下：
a
aa
ab
我们把纸上打印出来的字符串从1开始顺序编号，一直到n。打字机有一个非常有趣的功能，在打字机中暗藏一个带数字的小键盘，在小键盘上输入两个数(x,y)（其中1≤x,y≤n），打字机会显示第x个打印的字符串在第y个打印的字符串中出现了多少次。
阿狸发现了这个功能以后很兴奋，他想写个程序完成同样的功能，你能帮助他么？

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

Output
输出m行，其中第i行包含一个整数，表示第i个询问的答案。

Sample Input

aPaPBbP
3
1 2
1 3
2 3

Sample Output

2
1
0

题目链接：BZOJ 2434
这题由于是存在子串的关系，可以容易想到用fail树，然后先考虑暴力做法：对于某一询问，将$y$串在字典树中的$|y|$个节点位置都加上$1$，然后此询问的答案就是以$x$串在字典树中的结束节点$u$为根的子树中$1$的个数，那么单点更新，子树求和肯定用$BIT$喽，那么暴力的伪代码差不多是：

1
2
3
4
5
6
7
8
9
10
11
12
13
....此处省略用一些估计很麻烦的方法记录每一个串在trie中的节点位置的操作.....
for (i = 0; i < q; ++i)
{
	for (j = 0; j < strlen(str[y]); ++j)
	{
		add(L[str[y][j]的对应节点位置], 1);
	}
	ans[i] = querysum(L[lastpos_u],R[lastpos_u]);
	for (j = 0; j < strlen(str[y]); ++j)//统计完肯定要撤销前面的操作
	{
		add(L[str[y][j]的对应节点位置], -1);
	}
}

这么一看复杂度还是不行，观察一下统计的过程可以发现在$query$的时候总是仅有一个$y$串是生效的，因此我们为什么不枚举$y$串，然后把跟$y$相关的询问一次性处理掉呢？那么可以发现离线是可以的，但是也不是随便离线的啊，然后又可以发现按照我们插入字典树的顺序，$y$串的顺序是正序递增的，这个性质挺好，那如果每一次$\mathbf P$操作的时候我们都保证当前只有$\mathbf P$出来的这一串留在树中就好了。
那么可以想到每一次插入新节点时对该位置加$1$；$\mathbf B$操作时返回父节点前把当前节点$-1$，$\mathbf P$时处理当前可能存在的查询就好了
代码：

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
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <bitset>
#include <string>
#include <stack>
#include <cmath>
#include <queue>
#include <set>
#include <map>
using namespace std;
#define INF 0x3f3f3f3f
#define LC(x) (x<<1)
#define RC(x) ((x<<1)+1)
#define MID(x,y) ((x+y)>>1)
#define fin(name) freopen(name,"r",stdin)
#define fout(name) freopen(name,"w",stdout)
#define CLR(arr,val) memset(arr,val,sizeof(arr))
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);
typedef pair<int, int> pii;
typedef long long LL;
const double PI = acos(-1.0);
const int N = 1e5 + 7;
struct Trie
{
    int nxt[26];
    int fail;
    void init()
    {
        for (int i = 0; i < 26; ++i)
            nxt[i] = -1;
        fail = 0;
    }
} L[N];
struct edge
{
    int to, nxt;
    edge() {}
    edge(int _to, int _nxt): to(_to), nxt(_nxt) {};
} E[N];
struct Node
{
    int x, id;
};
vector<Node>Q[N];
int sz, pos[N], id;
int head[N], tot;
int in[N], out[N], idx, T[N], pre[N];
char s[N];
int ans[N];

void init()
{
    sz = 0;
    L[sz++].init();
    id = 0;
    CLR(head, -1);
    tot = 0;
    idx = 0;
    CLR(T, 0);
    for (int i = 0; i < N; ++i)
        if (!Q[i].empty())
            Q[i].clear();
}
inline void add(int s, int t)
{
    E[tot] = edge(t, head[s]);
    head[s] = tot++;
}
void dfs(int u, int f)
{
    in[u] = ++idx;
    for (int i = head[u]; ~i; i = E[i].nxt)
    {
        int v = E[i].to;
        if (v != f)
            dfs(v, u);
    }
    out[u] = idx;
}
namespace ac
{
    void ins(char s[], int len)
    {
        int u = 0;
        for (int i = 0; i < len; ++i)
        {
            if (s[i] == 'P')
                pos[++id] = u;//pos记录了第i个串的结束节点位置
            else if (s[i] == 'B')
                u = pre[u];
            else
            {
                int v = s[i] - 'a';
                if (L[u].nxt[v] == -1)
                {
                    L[sz].init();
                    L[u].nxt[v] = sz++;
                }
                pre[L[u].nxt[v]] = u;
                u = L[u].nxt[v];
            }
        }
    }
    void build()
    {
        queue<int>Q;
        for (int i = 0; i < 26; ++i)
        {
            int v = L[0].nxt[i];
            if (~v)
            {
                L[v].fail = 0;
                Q.push(v);
            }
            else
                L[0].nxt[i] = 0;
        }
        while (!Q.empty())
        {
            int u = Q.front();
            Q.pop();
            int uf = L[u].fail;
            for (int i = 0; i < 26; ++i)
            {
                int v = L[u].nxt[i];
                if (~v)
                {
                    L[v].fail = L[uf].nxt[i];
                    Q.push(v);
                }
                else
                    L[u].nxt[i] = L[uf].nxt[i];
            }
        }
    }
}
namespace bit
{
    void add(int k, int v)
    {
        while (k < N)
        {
            T[k] += v;
            k += (k & -k);
        }
    }
    int sum(int k)
    {
        int ret = 0;
        while (k)
        {
            ret += T[k];
            k -= (k & -k);
        }
        return ret;
    }
    int query(int l, int r)
    {
        return sum(r) - sum(l - 1);
    }
}
int main(void)
{
    int i, j;
    while (~scanf("%s", s))
    {
        init();
        int len = strlen(s);
        ac::ins(s, len);
        ac::build();
        for (i = 1; i < sz; ++i)
            add(L[i].fail, i);
        dfs(0, -1);
        int q;
        scanf("%d", &q);
        for (i = 0; i < q; ++i)
        {
            int x, y;
            scanf("%d%d", &x, &y);
            Q[y].push_back((Node) {x, i});
        }
        int Y = 0;
        int u = 0;
        for (i = 0; i < len; ++i)
        {
            if (s[i] == 'P')
            {
                ++Y;
                int m = Q[Y].size();
                for (j = 0; j < m; ++j)
                {
                    int qid = Q[Y][j].id;
                    int x = pos[Q[Y][j].x];
                    ans[qid] = bit::query(in[x], out[x]);
                }
            }
            else if (s[i] == 'B')
            {
                bit::add(in[u], -1);
                u = pre[u];
            }
            else
            {
                u = L[u].nxt[s[i] - 'a'];
                bit::add(in[u], 1);
            }
        }
        for (i = 0; i < q; ++i)
            printf("%d\n", ans[i]);
    }
    return 0;
}