bzoj2434: [Noi2011]阿貍的打字機
Description
阿貍喜歡收藏各種稀奇古怪的東西，最近他淘到一臺老式的打字機。打字機上只有28個按鍵，分別印有26個小寫英文字母和’B’、’P’兩個字母。
經阿貍研究發(fā)現(xiàn)，這個打字機是這樣工作的：
l 輸入小寫字母，打字機的一個凹槽中會加入這個字母(這個字母加在凹槽的最后)。
l 按一下印有’B’的按鍵，打字機凹槽中最后一個字母會消失。
l 按一下印有’P’的按鍵，打字機會在紙上打印出凹槽中現(xiàn)有的所有字母并換行，但凹槽中的字母不會消失。
例如，阿貍輸入aPaPBbP，紙上被打印的字符如下：
a
aa
ab
我們把紙上打印出來的字符串從1開始順序編號，一直到n。打字機有一個非常有趣的功能，在打字機中暗藏一個帶數(shù)字的小鍵盤，在小鍵盤上輸入兩個數(shù)(x,y)（其中1≤x,y≤n），打字機會顯示第x個打印的字符串在第y個打印的字符串中出現(xiàn)了多少次。
阿貍發(fā)現(xiàn)了這個功能以后很興奮，他想寫個程序完成同樣的功能，你能幫助他么？
輸入的第一行包含一個字符串，按阿貍的輸入順序給出所有阿貍輸入的字符。
第二行包含一個整數(shù)m，表示詢問個數(shù)。
接下來m行描述所有由小鍵盤輸入的詢問。其中第i行包含兩個整數(shù)x, y，表示第i個詢問為(x, y)。
Output
輸出m行，其中第i行包含一個整數(shù)，表示第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個打印的串中出現(xiàn)了多少次。
題解
首先考慮建立一棵trie樹來完成三種操作。 維護一個指針， 操作1：在trie樹上新建一個節(jié)點（若有則不用），指針指向這個節(jié)點。 操作2：指針指向當前節(jié)點的父親節(jié)點。 操作3：在當前指向的節(jié)點標記這是第幾個串的結尾。 那么如何處理詢問呢？一個很暴力的想法，對于串y的每個節(jié)點，沿著fail指針向回找，如果能找到串x的結尾，則ans++。 這樣很明顯是TLE的。 不難想到fail指針反向后是一棵樹，那么答案就是在串x的結尾在fail樹中所對應的子樹里有多少個屬于y的節(jié)點。而這棵子樹在fail樹的dfs序中肯定對應的是一段連續(xù)的區(qū)間，那么用樹狀數(shù)組就可以優(yōu)化時間了。 而這樣明顯不完美，考慮到在dfs序的樹狀數(shù)組中如過串y的每個節(jié)點都已經加入，那么所有對于串y的詢問都可以log時間內求出，所以將所有y相同的詢問連成一個鏈表一起處理。 那么就可以想出這樣一個思路： 在構建好fail樹之后，進行一邊dfs，對于每個節(jié)點u記錄進棧的時間戳l[u]和出棧的時間戳r[u]，建立一棵線段樹。 再掃描一遍操作序列： 操作1：走向下一個節(jié)點，該節(jié)點l[u]加入樹狀數(shù)組。 操作2：走向當前節(jié)點的父親節(jié)點，該節(jié)點的l[u]從樹狀數(shù)組中刪除。 操作3：對于所有y是當前串的詢問處理答案，答案即為 sum(r[x結尾節(jié)點])?sum(l[x結尾節(jié)點]?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++)
