CF547E Mike and Friends

题解
后缀数组, 字符串, 树状数组

Description

给定 $ n $ 个串 $ s_1, s_2, \cdots, s_n $ 和 $q$ 个询问，每次查询 $ s_i $ 一共在 $ s_l, s_{l+1}, \cdots, s_r $ 出现了多少次。

$ n, q, \sum \limits_{i=1}^{n} |s_i| \leq 2 \times 10^5 $。

Solution

这里有一个后缀数组的做法。

  • 把 $ n $ 个串依次连在一起，相邻两个之间用一个 # 隔开。得到一个大串 $ \mathtt{S} $ 。
  • 我们可以简单地求出第 $ i $ 个串 $ s_i $ 的长度 $len_i$，在 $ \mathtt{S} $ 中第一个字母所在的位置 $pos_i$ 以及 $ \mathtt{S} $ 的后缀数组。
  • 对于一个询问，假设询问串是 $s_k$，他在一个位置 $p$ 出现当且仅当从 $p$ 开始的后缀与从 $pos_k$ 开始的后缀的 $\mathtt{LCP} $ 的长度 $\ge len_k $ 。
  • 众所周知，两个后缀 $i, j (\mathtt{rk[i]} < \mathtt{rk[j]})$ 的 $ \mathtt{LCP} $ 就是 $\min\limits_{\mathtt{rk[i] + 1} \le x \le \mathtt{rk[j]}} \{\mathtt{height[x]}\}$ ，也就是一段区间的最小值。
  • 对于每个 $k$ ，我们可以简单地通过二分来找到最长的一段包含 $\mathtt{rk[k]}$ 的区间 $[L_k, R_k]$ 使得这一段区间中的 $\mathtt{height[i]}$ 最小值 $ \ge len_i$ 。
  • 那么如果一个后缀的前缀是 $s_k$ ，那么他的 $ \mathtt{rk} $ 必须要在 $[L_k, R_k]$ 中。
  • 而我们想要的是 $s_l, s_{l+1}, \cdots, s_r$ 中出现了多少次 $s_k$ ，所以这个后缀的出现位置 $i$ 要满足 $pos_l \le i \le pos_{r+1}-1$ 。为了方便，我们假设 $pos_{n+1} = |S|+1$ 。
  • 做法已经比较显然：如果把后缀 $i$ 对应成平面直角坐标系中的点 $(i, rk_i)$ ，那么对于一个询问 $l, r, k$ ，答案便是左下角为 $(pos_l, L_k)$ ，右上角为 $(pos_{r+1}-1, R_k)$ 的矩形中点的个数。
  • 这便是一个经典问题。只需要把一个询问拆成四个，拿出来按照第一关键字排序，按照顺序扫一遍，对于每个新的询问把满足第一维限制的点的第二维坐标加一，询问就查询前缀和即可。可以用一个简单的树状数组维护。
  • 时间复杂度 $O(n \log n)$ 。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
/**
 * Author: AcFunction
 * Date:   2019-08-20 12:57:11
 * Email:  3486942970@qq.com
**/

#include <bits/stdc++.h>
#define ll long long
#define db double
#define PII pair <int, int> 
#define pb push_back 
#define fi first
#define se second 
#define MP make_pair

using namespace std;

const int N = 1002000; 

int n, qq, m, rk[N], sa[N], cnt[N], c[N]; 
int len[N], pos[N], h[N], st[N][25], lg2[N], ans[N];
char s[N];  
string S; 
char A[N]; 
int Lp[N], Rp[N], tot; 

struct node {
  int x, y, id; 
} a[N], b[N]; 

struct Query {
  int x, y, id, typ; 
  bool operator < (const Query &t) const {
    return x == t.x ? y < t.y : x < t.x; 
  }
} Q[N * 4]; 

int lcp(int l, int r) {
  if(l > r) return -1; int k = lg2[r - l + 1]; 
  return min(st[l][k], st[r - (1 << k) + 1][k]); 
}

int lb(int x) {
  return x & (-x); 
}

int add(int x, int d) {
  for(int i = x; i <= m; i += lb(i)) 
    c[i] += d;
}

int sum(int x) {
  int ret = 0; 
  for(int i = x; i; i -= lb(i))
    ret += c[i]; 
  return ret; 
}

int main() {
  scanf("%d %d", &n, &qq);
  int nowlen = 1;  
  for(int i = 1; i <= n; i++) {
    pos[i] = nowlen; 
    scanf("%s", s + 1); 
    len[i] = strlen(s + 1); 
    for(int j = 1; j <= len[i]; j++) 
      S += s[j]; 
    nowlen += len[i] + 1; 
    S += '#';  
  } 
  m = S.length();   
  pos[n + 1] = m + 1;
  A[0] = '#'; 
  for(int i = 0; i < m; i++) A[i + 1] = S[i]; 
  for(int i = 1; i <= m; i++) cnt[A[i]]++; 
  for(int i = 1; i <= 256; i++) cnt[i] += cnt[i - 1]; 
  for(int i = 1; i <= m; i++) rk[i] = cnt[A[i]]; 
  for(int L = 1; L <= m; L <<= 1) {
    for(int i = 1; i <= m; i++) {
      a[i].x = rk[i], a[i].y = rk[i + L]; a[i].id = i;
    }
    for(int i = 1; i <= m; i++) cnt[i] = 0; 
    for(int i = 1; i <= m; i++) cnt[a[i].y]++; 
    for(int i = 1; i <= m; i++) cnt[i] += cnt[i - 1]; 
    for(int i = 1; i <= m; i++) b[cnt[a[i].y]--] = a[i]; 
    for(int i = 1; i <= m; i++) cnt[i] = 0; 
    for(int i = 1; i <= m; i++) cnt[b[i].x]++;
    for(int i = 1; i <= m; i++) cnt[i] += cnt[i - 1]; 
    for(int i = m; i >= 1; i--) a[cnt[b[i].x]--] = b[i]; 
    for(int i = 1; i <= m; i++) {
      if(a[i].x == a[i - 1].x && a[i].y == a[i - 1].y)
        rk[a[i].id] = rk[a[i - 1].id]; 
      else rk[a[i].id] = rk[a[i - 1].id] + 1; 
    }
  }
  for(int i = 2; i <= m; i++) lg2[i] = lg2[i >> 1] + 1; 
  for(int i = 1; i <= m; i++) sa[rk[i]] = i; 
  int k = 0; 
  for(int i = 1; i <= m; i++) {
    if(k) k--; int j = sa[rk[i] - 1]; 
    while(i + k <= m && j + k <= m && A[i + k] == A[j + k]) k++;
    h[rk[i]] = k; 
  }
  for(int i = 1; i <= m; i++) st[i][0] = h[i]; 
  for(int j = 1; (1 << j) <= m; j++) 
    for(int i = 1; i + (1 << j) - 1 <= m; i++) 
      st[i][j] = min(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]); 
  for(int i = 1; i <= n; i++) {
    int pp = pos[i];
    int l = rk[pp] + 1, r = m; 
    Lp[i] = Rp[i] = rk[pp]; 
    while(l <= r) {
      int mid = (l + r) >> 1; 
      if(lcp(rk[pp] + 1, mid) >= len[i]) {
        Rp[i] = mid; l = mid + 1;  
      } else r = mid - 1; 
    }
    l = 1, r = rk[pp]; 
    while(l <= r) {
      int mid = (l + r) >> 1; 
      if(lcp(mid + 1, rk[pp]) >= len[i]) {
        Lp[i] = mid; r = mid - 1; 
      } else l = mid + 1; 
    }  
  }
  for(int i = 1; i <= qq; i++) {
    int l, r, k; 
    scanf("%d %d %d", &l, &r, &k); 
    Q[++tot] = {pos[l] - 1, Lp[k] - 1, i, 1}; 
    Q[++tot] = {pos[r + 1] - 1, Lp[k] - 1, i, -1}; 
    Q[++tot] = {pos[l] - 1, Rp[k], i, -1}; 
    Q[++tot] = {pos[r + 1] - 1, Rp[k], i, 1}; 
  }
  int P = 1; 
  sort(Q + 1, Q + tot + 1);
  for(int i = 1; i <= tot; i++) {
    while(P <= Q[i].x && P <= m) {
      add(rk[P], 1); P++; 
    }
    // cout << Q[i].x << " " << Q[i].y << endl; 
    // cout << P << endl; 
    ans[Q[i].id] += Q[i].typ * sum(Q[i].y); 
  }
  for(int i = 1; i <= qq; i++) printf("%d\n", ans[i]); 
  return 0; 
}