卧槽，写了一个小时的代码，终于把题目做出来了

智猫（已退）

洛谷P2414

1. #include <cstdio>
   
2. #include <vector>
   
3. #include <queue>
   
4. using namespace std;
   
5. const int maxn = 100010;
   
6. const int maxc = 30;
   
7. struct BIT {
   
8.     int n, t[maxn];
   
9.     void update(int k, int x) {
   
10.         for (int i = k; i <= n; i += i & (-i)) {
    
11.             t[i] += x;
    
12.         }
    
13.     }
    
14.     int query(int x) {
    
15.         int ans = 0;
    
16.         for (int i = x; i >= 1; i -= i & (-i)) {
    
17.             ans += t[i];
    
18.         }
    
19.         return ans;
    
20.     }
    
21. } bt;
    
22. struct ACTrie {
    
23.     int ch[maxn][maxc], cch[maxn][maxc], fa[maxn], tot = 1;
    
24.     int insert(char s[]) {
    
25.         int p = 1;
    
26.         for (int i = 0; s[i]; i++) {
    
27.             if (!ch[p][s[i] - 'a']) {
    
28.                 ch[p][s[i] - 'a'] = ++tot;
    
29.             }
    
30.             p = ch[p][s[i] - 'a'];
    
31.         }
    
32.         return p;
    
33.     }
    
34.     int fail[maxn];
    
35.     vector<int> failson[maxn];
    
36.     int id[maxn], dfn[maxn], dfe[maxn], times = 0;
    
37.     queue<int> q;
    
38.     void init() {
    
39.         fail[1] = 1;
    
40.         for (int i = 0; i < 26; i++) {
    
41.             if (ch[1][i]) {
    
42.                 q.push(ch[1][i]);
    
43.                 fail[ch[1][i]] = 1;
    
44.                 failson[1].push_back(ch[1][i]);
    
45.             } else {
    
46.                 ch[1][i] = 1;
    
47.             }
    
48.         }
    
49.         while (!q.empty()) {
    
50.             int t = q.front();
    
51.             q.pop();
    
52.             for (int i = 0; i < 26; i++) {
    
53.                 if (ch[t][i]) {
    
54.                     q.push(ch[t][i]);
    
55.                     fail[ch[t][i]] = ch[fail[t]][i];
    
56.                     failson[ch[fail[t]][i]].push_back(ch[t][i]);
    
57.                 } else {
    
58.                     ch[t][i] = ch[fail[t]][i];
    
59.                 }
    
60.             }
    
61.         }
    
62.     }
    
63.     void dfsfail(int u) {
    
64.         id[++times] = u;
    
65.         dfn[u] = times;
    
66.         for (int v : failson[u]) {
    
67.             if (v != u)
    
68.             dfsfail(v);
    
69.         }
    
70.         dfe[u] = times;
    
71.     }
    
72.     void buildac() {
    
73.         init();
    
74.         dfsfail(1);
    
75.     }
    
76. } act;
    
77. int n, k, x, y;
    
78. int ed[100010];
    
79. vector<int> id[100010];
    
80. char s[100010], c;
    
81. int ans[100010];
    
82. vector<pair<int, int> > queries[100010];
    
83. void dfs(int u) {
    
84.     bt.update(act.dfn[u], 1);
    
85.     for (int v : id[u]) {
    
86.         for (auto l : queries[v]) {
    
87.             ans[l.second] = bt.query(act.dfe[ed[l.first]]) - bt.query(act.dfn[ed[l.first]] - 1);
    
88.         }
    
89.     }
    
90.     for (int i = 0; i < 26; i++) {
    
91.         if (act.cch[u][i]) {
    
92.             dfs(act.cch[u][i]);
    
93.         }
    
94.     }
    
95.     bt.update(act.dfn[u], -1);
    
96. }
    
97. int main() {
    
98.     scanf("%s", s);
    
99.     int p = 1;
    
100.     for (int i = 0; s[i]; i++) {
     
101.         if (s[i] == 'B') {
     
102.             p = act.fa[p];
     
103.         } else if (s[i] == 'P') {
     
104.             ed[++k] = p;
     
105.             id[p].push_back(k);
     
106.         } else {
     
107.             if (!act.ch[p][s[i] - 'a']) {
     
108.                 act.ch[p][s[i] - 'a'] = ++act.tot;
     
109.                 act.cch[p][s[i] - 'a'] = act.tot;
     
110.                 act.fa[act.ch[p][s[i] - 'a']] = p;
     
111.             }
     
112.             p = act.ch[p][s[i] - 'a'];
     
113.         }
     
114.     }
     
115.     act.buildac();
     
116.     bt.n = act.tot;
     
117.     scanf("%d", &n);
     
118.     for (int i = 1; i <= n; i++) {
     
119.         scanf("%d%d", &x, &y);
     
120.         queries[y].push_back({x, i});
     
121.     }
     
122.     dfs(1);
     
123.     for (int i = 1; i <= n; i++) {
     
124.         printf("%d\n", ans[i]);
     
125.     }
     
126.     return 0;
     
127. }

复制代码

四十四次日落

这代码是干嘛的

四十四次日落

hhh