bzoj2434: [Noi2011]阿狸的打字机
Description
阿狸喜欢收藏各种稀奇古怪的东西，最近他淘到一台老式的打字机。打字机上只有28个按键，分别印有26个小写英文字母和’B’、’P’两个字母。
经阿狸研究发现，这个打字机是这样工作的：
l 输入小写字母，打字机的一个凹槽中会加入这个字母(这个字母加在凹槽的最后)。
l 按一下印有’B’的按键，打字机凹槽中最后一个字母会消失。
l 按一下印有’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
题意
初始串为空，给出三种操作： 1.向串尾加入一个字符 2.删除串尾最后一个字符 3.打印当前串 多次询问第x个打印的串在第y个打印的串中出现了多少次。
题解
首先考虑建立一棵trie树来完成三种操作。 维护一个指针， 操作1：在trie树上新建一个节点（若有则不用），指针指向这个节点。 操作2：指针指向当前节点的父亲节点。 操作3：在当前指向的节点标记这是第几个串的结尾。 那么如何处理询问呢？一个很暴力的想法，对于串y的每个节点，沿着fail指针向回找，如果能找到串x的结尾，则ans++。 这样很明显是TLE的。 不难想到fail指针反向后是一棵树，那么答案就是在串x的结尾在fail树中所对应的子树里有多少个属于y的节点。而这棵子树在fail树的dfs序中肯定对应的是一段连续的区间，那么用树状数组就可以优化时间了。 而这样明显不完美，考虑到在dfs序的树状数组中如过串y的每个节点都已经加入，那么所有对于串y的询问都可以log时间内求出，所以将所有y相同的询问连成一个链表一起处理。 那么就可以想出这样一个思路： 在构建好fail树之后，进行一边dfs，对于每个节点u记录进栈的时间戳l[u]和出栈的时间戳r[u]，建立一棵线段树。 再扫描一遍操作序列： 操作1：走向下一个节点，该节点l[u]加入树状数组。 操作2：走向当前节点的父亲节点，该节点的l[u]从树状数组中删除。 操作3：对于所有y是当前串的询问处理答案，答案即为 sum(r[x结尾节点])−sum(l[x结尾节点]−1)
#include<cstdio>#include<iostream>#include<cstring>#include<queue>#include<vector>using namespace std;const int max_size = 100000 + 10, ch_size = 26;inline void in(int &x);struct Query{ int x, y, next; Query() {x = y = next = 0;}}qry[max_size];int lstq[max_size], ans[max_size];char s[max_size];int m;int clk, c[max_size<<1];void add(int x, int d){ while(x <= clk){ c[x] += d; x += (x&-x); }}int sum(int x){ int cnt = 0; while(x){ cnt += c[x]; x -= (x&-x); } return cnt;}struct Trie{ int ch[max_size][ch_size]; int f[max_size], val[max_size]; int l[max_size], r[max_size], fa[max_size], pos[max_size]; vector<int> ft[max_size]; int idx['z'+1]; int sz; Trie() {clk = 0; sz = 1; for(char i = 'a'; i <= 'z'; i++) idx[i] = i-'a';} void insert(char *s){ int tot = 0, u = 0, len = strlen(s); for(int i = 0; i < len; i++){ if(s[i] == 'B'){ u = fa[u]; continue; } if(s[i] == 'P'){ val[u] = ++tot; pos[tot] = u; continue; } int x = idx[s[i]]; if(!ch[u][x]){ ch[u][x] = sz++; fa[ch[u][x]] = u; } u = ch[u][x]; } } void get_fail(){ queue<int> q; for(int i = 0; i < ch_size; i++){ int u = ch[0][i]; if(u){ f[u] = 0; q.push(u); ft[0].push_back(u); } } while(!q.empty()){ int r = q.front(); q.pop(); for(int i = 0; i < ch_size; i++){ int &u = ch[r][i]; if(!u) continue; int v = f[r]; while(v && !ch[v][i]) v = f[v]; f[u] = ch[v][i]; ft[ch[v][i]].push_back(u); q.push(u); } } } void dfs(int now){ l[now] = ++clk; int n = ft[now].size(); for(int i = 0; i < n; i++) dfs(ft[now][i]); r[now] = ++clk; } void solve(char *s){ int u = 0, num = 0, len = strlen(s); for(int i = 0; i < len; i++){ if(s[i] == 'P'){ num++; for(int j = lstq[num]; j; j = qry[j].next){ int k = pos[qry[j].x]; ans[j] = sum(r[k]) - sum(l[k] - 1); } } else if(s[i] == 'B'){ add(l[u], -1); u = fa[u]; } else{ u = ch[u][idx[s[i]]]; add(l[u], 1); } } }}ac;void init(){ scanf("%s %d", s, &m); int x, y; for(int i = 1; i <= m; i++){ in(x); in(y); qry[i].x = x; qry[i].y = y; qry[i].next = lstq[y]; lstq[y] = i; }}void work(){ ac.insert(s); ac.get_fail(); ac.dfs(0); ac.solve(s); for(int i = 1; i <= m; i++) PRintf("%d/n", ans[i]);}int main(){ init(); work(); return 0;}void in(int &x){ x = 0; char c; c = getchar(); while(c < '0' || c > '9') c = getchar(); while(c >= '0' && c <= '9') {x = x * 10 + (c - '0'); c = getchar();}}
