bzoj 2434 阿狸的打字机 - Aho-Corasick自动机 - 树状数组

题目传送门

　　传送站I

　　传送站II

题目大意

　　阿狸有一个打字机，它有3种键：

1. 向缓冲区追加小写字母
2. P：打印当前缓冲区（缓冲区不变）
3. B：删除缓冲区中最后一个字符

　　然后多次询问第$x$个被打印出来的串在第$y$个被打印出来的串中出现多少次。

　　每次查询相当于询问串$x$的结束节点在fail树中的子树包含多少串$y$的点。

　　又因为这些串的构造比较另类。所以考虑把询问离线，然后用树状数组维护子树中关键点的个数。

Code

 /**

  * bzoj

  * Problem#2434

  * Accepted

  * Time: 620ms

  * Memory: 17792k

  */

 #include <algorithm>

 #include <iostream>

 #include <cstdlib>

 #include <cstdio>

 #include <vector>

 #include <queue>

 #include <stack>

 using namespace std;

 typedef bool boolean;

 const int N = 1e5 + ;

 typedef class IndexedTree {

     public:

         int s;

         int ar[N];

         void add(int idx, int val) {

             for ( ; idx <= s; idx += (idx & (-idx)))

                 ar[idx] += val;

         }

         int getSum(int idx) {

             int rt = ;

             for ( ; idx; idx -= (idx & (-idx)))

                 rt += ar[idx];

             return rt;

         }

 }IndexedTree;

 typedef class TrieNode {

     public:

         int in, out;

         TrieNode* ch[];

         TrieNode* fail;

 }TrieNode;

 TrieNode pool[N];

 TrieNode *top = pool;

 TrieNode* newnode() {

     return ++top;

 }

 typedef class AhoCorasick {

     public:

         TrieNode *rt;

         AhoCorasick():rt(newnode()) {    }

         void travel(char* str, TrieNode** ts) {

             stack<TrieNode*> s;

             TrieNode* p;

             s.push(rt);

             for (int i = , c, cp = ; str[i]; i++) {

                 if (str[i] == 'B')

                     s.pop();

                 else if (str[i] == 'P')

                     ts[++cp] = s.top();

                 else {

                     p = s.top(), c = str[i] - 'a';

                     if (!p->ch[c])

                         p->ch[c] = newnode();

                     s.push(p->ch[c]);

                 }

             }

         }

         void build(vector<int> *g) {

             queue<TrieNode*> que;

             que.push(rt);

             while (!que.empty()) {

                 TrieNode* p = que.front();

                 que.pop();

                 for (int i = ; i < ; i++) {

                     TrieNode *np = p->ch[i], *f = p->fail;

                     if (!np)    continue;

                     while (f && !f->ch[i])    f = f->fail;

                     if (!f)

                         np->fail = rt;

                     else

                         np->fail = f->ch[i];

                     que.push(np);

                 }

             }

             for (TrieNode* p = top; p != pool + ; p--)

                 g[p->fail - pool].push_back(p - pool);

         }

 }AhoCorasick;

 typedef class Query {

     public:

         int x, y, id;

         boolean operator < (Query b) const {

             return y < b.y;

         }

 }Query;

 int m, cnt = ;

 char str[N];

 int *res;

 Query *qs;

 TrieNode** ts;

 vector<int> g[N];

 IndexedTree it;

 AhoCorasick ac;

 inline void init() {

     gets(str);

     scanf("%d", &m);

     qs = new Query[(m + )];

     res = new int[(m + )];

     ts = new TrieNode*[(m + )];

     for (int i = ; i <= m; i++) {

         scanf("%d%d", &qs[i].x, &qs[i].y);

         qs[i].id = i;

     }

 }

 void dfs(int p) {

     pool[p].in = ++cnt;

     for (int i = ; i < (signed) g[p].size(); i++)

         dfs(g[p][i]);

     pool[p].out = cnt;

 }

 inline void solve() {

     ac.travel(str, ts);

     ac.build(g);

     it.s = (top - pool + );

     dfs();

     sort(qs + , qs + m + );

     stack<TrieNode*> s;

     s.push(ac.rt);

     for (int i = , cur = , cq = ; cq <= m && str[i]; i++) {

         TrieNode *p = s.top();

         if (str[i] == 'B') {

             it.add(p->in, -);

             s.pop();

         } else if (str[i] == 'P') {

             cur++;

             while (cq <= m && qs[cq].y == cur)

                 res[qs[cq].id] = it.getSum(ts[qs[cq].x]->out) - it.getSum(ts[qs[cq].x]->in - ), cq++;

         } else {

             p = p->ch[str[i] - 'a'];

             it.add(p->in, );

             s.push(p);

         }

     }

     for (int i = ; i <= m; i++)

         printf("%d\n", res[i]);

 }

 int main() {

     init();

     solve();

     return ;

 }