「BZOJ2434」[NOI2011]阿狸的打字机

Description

阿狸喜欢收藏各种稀奇古怪的东西，最近他淘到一台老式的打字机。打字机上只有 $28$ 个按键，分别印有 $26$ 个小写英文字母和 B 、 P 两个字母。经阿狸研究发现，这个打字机是这样工作的：

输入小写字母，打字机的一个凹槽中会加入这个字母(按 P 前凹槽中至少有一个字母)。
按一下印有 B 的按键，打字机凹槽中最后一个字母会消失。
按一下印有 P 的按键，打字机会在纸上打印出凹槽中现有的所有字母并换行，但凹槽中的字母不会消失（保证凹槽中至少有一个字母）。

例如，阿狸输入 aPaPBbP ，纸上被打印的字符如下：

a 
aa 
ab

我们把纸上打印出来的字符串从 $1$ 开始顺序编号，一直到 $n$ 。打字机有一个非常有趣的功能，在打字机中暗藏一个带数字的小键盘，在小键盘上输入两个数 $(x,y)$ （其中 $1 \le x,y \le 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

HINT

所有测试数据的范围和特点如下表所示：

测试点编号	$n$ 的规模	$m$ 的规模	字符串长度	输入总长 (输入文件第一行的字符数)
1	$1\le n \le 100$	$1\le m \le 1000$	-	$\le 100$
2	$1\le n \le 100$	$1\le m \le 1000$	-	$\le 100$
3	$1\le n \le 1000$	$1\le m \le 10^4$	单个长度 $\le 1000$ ，总长度 $\le 10^5$	$\le 10^5$
4	$1\le n \le 1000$	$1\le m \le 10^4$	单个长度 $\le 1000$ ，总长度 $\le 10^5$	$\le 10^5$
5	$1\le n \le 10^4$	$1\le m \le 10^5$	总长度 $\le 10^5$	$\le 10^5$
6	$1\le n \le 10^4$	$1\le m \le 10^5$	总长度 $\le 10^5$	$\le 10^5$
7	$1\le n \le 10^4$	$1\le m \le 10^5$	总长度 $\le 10^5$	$\le 10^5$
8	$1\le n \le 10^5$	$1\le m \le 10^5$	-	$\le 10^5$
9	$1\le n \le 10^5$	$1\le m \le 10^5$	-	$\le 10^5$
10	$1\le n \le 10^5$	$1\le m \le 10^5$	-	$\le 10^5$

Solution

force

对于每一个询问按照 $y$ 排序一遍，然后相同的 $y$ 用同义词遍历的solve得到的 $sum$ 数组统计答案即可。

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<map>
#include<bitset>
#include<queue>
#define mk make_pair
#define fi first
#define nd second
#define pii pair<int,int>
#define pb push_back
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
inline ll read() {ll x = 0; char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}
const int N = 1e6;

char s[N];
int n;
int ch[N][26], tot, fa[N], pos[N];
int cnt[N], m;
vector<int> v[N];
int fail[N];
void getfail() {
    queue<int>q;
    for(int i = 0; i < 26; ++i) if(ch[0][i]) q.push(ch[0][i]);
    while(!q.empty()) {
        int x = q.front(); q.pop();
        for(int i = 0; i < 26; ++i) {
            if(ch[x][i]) {
                fail[ch[x][i]] = ch[fail[x]][i];
                q.push(ch[x][i]);
            }
            else ch[x][i] = ch[fail[x]][i];
        }
    }
}
struct TT {
    int x, y, i;
}t[N];
bool cmp(TT _x, TT _y) {
    return _x.y < _y.y;
}
int sum[N], st[N], top, ans[N];
bool vis[N];
void solve(int x) {
    x = pos[x];
    while(x) {
        for(int j = x; j; j = fail[j]) for(int k = 0; k < v[j].size(); ++k) {
            ++sum[v[j][k]];
            if(!vis[v[j][k]]) {
                vis[v[j][k]] = 1;
                st[++top] = v[j][k];
            }
        }
        x = fa[x];
    }
}
int main() {
    int now = 0;
    scanf("%s",s + 1);
    n = strlen(s + 1);
    for(int i = 1; i <= n; ++i) {
        if(s[i] >= 'a' && s[i] <= 'z') {
            int to = s[i] - 'a';
            if(!ch[now][to]) ch[now][to] = ++tot, fa[tot] = now;
            now = ch[now][to];
        }
        if(s[i] == 'B') now = fa[now];
        if(s[i] == 'P')
            v[now].pb(++m), pos[m] = now;
    }
    getfail();
    int Q = read();
    for(int i = 1; i <= Q; ++i)
        t[i].x= read(), t[i].y = read(), t[i].i= i;
    sort(t +1, t +1 +Q, cmp);
    for(int i = 1, j; i <= Q; i = j) {
        j = i;
        solve(t[i].y);
        while(t[j].y == t[i].y) {
            ans[t[j].i] = sum[t[j].x];
            ++j;
        }
        while(top) {
            vis[st[top]] = 0;
            sum[st[top--]] = 0;
        }
    }
    for(int i = 1; i <= Q; ++i)
        writeln(ans[i]);
    return 0;
}

std

对于询问 $(x,y)$ ，求 $x$ 在 $y$ 里出现过几次，相当于在原来 $trie$ 树上跑 $y$ 这条链，然后跑链上的每一个节点的 $fail$ 来统计答案。实际上就是枚举 $y$ 的前缀，然后找前缀的后缀就是找 $x$ 了。
换一句话说对于一个循环 $(x,y)$ 就是要从 $x$ 出发经过 $fail$ 边一共可以到达多少个 $y$ 链上的点。
我们可以模拟一遍 $dfs$ 很显然当前到达的节点即 $0$ 到其路径的链，所以直接用树状数组查询即可。

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<map>
#include<bitset>
#include<queue>
#define mk make_pair
#define fi first
#define nd second
#define pii pair<int,int>
#define pb push_back
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
inline ll read() {ll x = 0; char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}
const int N = 1e6;

char s[N];
int n;
int ch[N][26], tot, fa[N], pos[N], CH[N][26];
int cnt[N], m;
vector<int> v[N];
int fail[N];
void getfail() {
    queue<int>q;
    for(int i = 0; i < 26; ++i) if(ch[0][i]) q.push(ch[0][i]);
    while(!q.empty()) {
        int x = q.front(); q.pop();
        for(int i = 0; i < 26; ++i) {
            if(ch[x][i]) {
                fail[ch[x][i]] = ch[fail[x]][i];
                q.push(ch[x][i]);
            }
            else ch[x][i] = ch[fail[x]][i];
        }
    }
}
struct TT {
    int x, y, i;
}t[N];
bool cmp(TT _x, TT _y) {
    return _x.y < _y.y;
}
struct Edge {
    int u, v, nxt;
}e[N * 2];
int head[N], en;
void addedge(int x, int y) {
    e[++en].u = x, e[en].v = y,e[en].nxt = head[x], head[x] = en;
}
int L[N], R[N], num;
void DFS(int x) {
    L[x] = ++num;
    for(int i = head[x]; i;i  =e[i].nxt) DFS(e[i].v);
    R[x] = num;
}
int c[N];
void add(int x, int v) {
    for(; x <= num; x += x & -x)
        c[x] += v;
}
int query(int x) {
    int res = 0;
    for(; x; x -= x & -x)
        res += c[x];
    return res;
}
int ans[N];
int ql[N], qr[N];
void solve(int x) {
    add(L[x], 1);
    if(ql[x]) {
        for(int i = ql[x]; i <= qr[x]; ++i) {
            ans[t[i].i] = query(R[t[i].x]) - query(L[t[i].x] - 1);
        }
    }
    for(int i = 0; i < 26; ++i)
        if(CH[x][i]) solve(CH[x][i]);
    add(L[x], -1);
}
int main() {
    int now = 0;
    scanf("%s",s + 1);
    n = strlen(s + 1);
    for(int i = 1; i <= n; ++i) {
        if(s[i] >= 'a' && s[i] <= 'z') {
            int to = s[i] - 'a';
            if(!ch[now][to]) ch[now][to] = ++tot, fa[tot] = now;
            now = ch[now][to];
        }
        if(s[i] == 'B') now = fa[now];
        if(s[i] == 'P')
            v[now].pb(++m), pos[m] = now;
    }
    for(int i = 0; i <= tot; ++i) memmove(CH[i], ch[i], sizeof ch[i]);
    getfail();
    for(int i = 1; i <= tot; ++i) addedge(fail[i], i);
    DFS(0);
    int Q = read();
    for(int i = 1; i <= Q; ++i)
        t[i].x= read(), t[i].y = read(), t[i].i= i;
    sort(t +1, t +1 +Q, cmp);
    for(int i = 1; i <= Q; ++i) {
        t[i].x = pos[t[i].x];
        t[i].y = pos[t[i].y];
    }
    for(int i  = 1, j; i <= Q; i = j) {
        j = i;
        ql[t[i].y] = i;
        while(t[j].y== t[i].y) ++j;
        qr[t[i].y] = j - 1;
    }
    solve(0);
    for(int i = 1; i <= Q; ++i)
        writeln(ans[i]);
    return 0;
}