题目传送门

  传送站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 ;
}
05-08 07:59