BZOJ 2434: [Noi2011]阿狸的打字机( AC自动机 + DFS序 + 树状数组 )

时间:2022-08-31 21:57:02

BZOJ 2434: [Noi2011]阿狸的打字机( AC自动机 + DFS序 + 树状数组 )

一个串a在b中出现, 那么a是b的某些前缀的后缀, 所以搞出AC自动机, 按fail反向建树, 然后查询(x, y)就是y的子树中有多少是x的前缀. 离线, 对AC自动机DFS一遍, 用dfs序+树状数组维护, DFS到的查询点就回答询问.时间复杂度O(|ACAM|+QlogQ)

-------------------------------------------------------------------------------------------

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<cctype>
 
using namespace std;
 
#define chk(c) ((c <= 'z' && c >= 'a') || (c =='P') || (c == 'B'))
#define C(c) (c - 'a')
 
const int maxn = 100009;
const int c = 26;
 
inline int read() {
char c = getchar();
for(; !isdigit(c); c = getchar());
int ret = 0;
for(; isdigit(c); c = getchar())
ret = ret * 10 + c - '0';
return ret;
}
 
struct Node {
Node *ch[c], *fail, *par;
int v, d;
Node() : v(0) {
memset(ch, 0, sizeof ch);
fail = par = 0;
}
} pool[maxn], *V[maxn], *pt = pool, *Rt;
 
struct Q {
int d, x, y;
inline void Read(int _d) {
d = _d;
x = read();
y = read();
}
bool operator < (const Q &o) const {
return y < o.y;
}
} q[maxn];
 
int n, dfsn, qn;
int L[maxn], R[maxn], ql[maxn], qr[maxn], ans[maxn];
 
void Init() {
int cnt = dfsn = n = 0;
pt->d = n++;
Rt = pt++;
Node* t = Rt;
char c = getchar();
for(; !chk(c); c = getchar());
for(; chk(c); c = getchar()) {
if(c == 'P') {
V[t->v = ++cnt] = t;
} else if(c == 'B') {
t = t->par;
} else {
if(!t->ch[C(c)]) {
pt->par = t;
pt->d = n++;
t->ch[C(c)] = pt++;
}
t = t->ch[C(c)];
}
}
scanf("%d", &qn);
for(int i = 0; i < qn; i++) 
q[i].Read(i);
sort(q, q + qn);
memset(ql, 0, sizeof(int) * (cnt + 1));
memset(qr, -1, sizeof(int) * (cnt + 1));
for(int i = 0; i < qn; i++) {
if(!i || q[i - 1].y != q[i].y)
ql[q[i].y] = i;
if(i + 1 == qn || q[i + 1].y != q[i].y)
qr[q[i].y] = i;
}
}
 
struct edge {
int to;
edge* next;
} E[maxn << 1], *Pt = E, *head[maxn];
 
inline void AddEdge(int u, int v) {
Pt->to = v;
Pt->next = head[u];
head[u] = Pt++;
}
 
queue<Node*> que;
 
void buildFail() {
que.push(Rt);
while(!que.empty()) {
Node* t = que.front(); que.pop();
if(t->fail)
AddEdge(t->fail->d, t->d);
for(int i = 0; i < c; i++) if(t->ch[i]) {
Node* f = t->fail;
while(f && !f->ch[i])
f = f->fail;
t->ch[i]->fail = f ? f->ch[i] : Rt;
que.push(t->ch[i]);
}
}
}
 
struct BIT {
int b[maxn];
BIT() {
memset(b, 0, sizeof b);
}
inline void Add(int x, int v) {
for(; x <= n; x += x & -x)
b[x] += v;
}
inline int Sum(int x) {
int ret = 0;
for(; x; x -= x & -x)
ret += b[x];
return ret;
}
inline int Query(int l, int r) {
return Sum(r) - Sum(l - 1);
}
} Bit;
 
void DFS(int x) {
L[x] = ++dfsn;
for(edge* e = head[x]; e; e = e->next) DFS(e->to);
R[x] = dfsn;
}
 
void dfsAC(Node* t) {
Bit.Add(L[t->d], 1);
if(t->v) {
for(int i = ql[t->v]; i <= qr[t->v]; i++)
ans[q[i].d] = Bit.Query(L[V[q[i].x]->d], R[V[q[i].x]->d]);
}
for(int i = 0; i < c; i++)
if(t->ch[i]) dfsAC(t->ch[i]);
Bit.Add(L[t->d], -1);
}
 
int main() {
Init();
buildFail();
DFS(0);
dfsAC(Rt);
for(int i = 0; i < qn; i++)
printf("%d\n", ans[i]);
return 0;
}

-------------------------------------------------------------------------------------------

2434: [Noi2011]阿狸的打字机

Time Limit: 10 Sec  Memory Limit: 256 MB
Submit: 1706  Solved: 974
[Submit][Status][Discuss]

Description

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

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

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

l 按一下印有'B'的按键,打字机凹槽中最后一个字母会消失。

l 按一下印有'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

HINT

1<=N<=10^5

1<=M<=10^5

输入总长<=10^5

Source