fork download
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3. #include <ext/pb_ds/tree_policy.hpp>
  4. using namespace __gnu_pbds;
  5. using namespace std;
  6. #define Foreach(i, c) for(__typeof((c).begin()) i = (c).begin(); i != (c).end(); ++i)
  7. #define For(i,a,b) for(int (i)=(a);(i) < (b); ++(i))
  8. #define rof(i,a,b) for(int (i)=(a);(i) > (b); --(i))
  9. #define rep(i, c) for(auto &(i) : (c))
  10. #define x first
  11. #define y second
  12. #define pb push_back
  13. #define PB pop_back()
  14. #define iOS ios_base::sync_with_stdio(false)
  15. #define sqr(a) (((a) * (a)))
  16. #define all(a) a.begin() , a.end()
  17. #define error(x) cerr << #x << " = " << (x) <<endl
  18. #define Error(a,b) cerr<<"( "<<#a<<" , "<<#b<<" ) = ( "<<(a)<<" , "<<(b)<<" )\n";
  19. #define errop(a) cerr<<#a<<" = ( "<<((a).x)<<" , "<<((a).y)<<" )\n";
  20. #define coud(a,b) cout<<fixed << setprecision((b)) << (a)
  21. #define L(x) ((x)<<1)
  22. #define R(x) (((x)<<1)+1)
  23. #define umap unordered_map
  24. #define double long double
  25. typedef long long ll;
  26. typedef pair<int,int>pii;
  27. typedef vector<int> vi;
  28. typedef complex<double> point;
  29. template <typename T> using os = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
  30. template <class T> inline void smax(T &x,T y){ x = max((x), (y));}
  31. template <class T> inline void smin(T &x,T y){ x = min((x), (y));}
  32. const int maxn = 5e5 + 100;
  33. int TRIE[maxn][26];
  34. string s[maxn];
  35. int f[maxn], aut[maxn][26], root, nx = 1;
  36. vi tof[maxn];
  37. int h[maxn];
  38. vi ver[maxn];
  39. vi adj[maxn];
  40. int end[maxn];
  41. inline void build(int x){
  42. int v = root;
  43. rep(ch, s[x]){
  44. int c = ch - 'a';
  45. if(TRIE[v][c] == -1){
  46. TRIE[v][c] = nx;
  47. h[nx] = h[v] + 1;
  48. ver[h[nx]].pb(nx);
  49. ++ nx;
  50. }
  51. v = TRIE[v][c];
  52. }
  53. ::end[x] = v;
  54. }
  55. inline void ahoc(){
  56. f[root] = root;
  57. For(h,0,maxn)
  58. rep(v, ver[h])For(c,0,26){
  59. if(TRIE[v][c] != -1){
  60. aut[v][c] = TRIE[v][c];
  61. if(v != root)
  62. f[aut[v][c]] = aut[f[v]][c];
  63. else
  64. f[aut[v][c]] = root;
  65. }
  66. else{
  67. if(v == root)
  68. aut[v][c] = root;
  69. else
  70. aut[v][c] = aut[f[v]][c];
  71. }
  72. }
  73. }
  74. inline void go(int x){
  75. int v = root;
  76. rep(ch, s[x]){
  77. int c = ch - 'a';
  78. v = aut[v][c];
  79. tof[v].pb(x);
  80. }
  81. }
  82. int par[maxn];
  83. int st[maxn], ft[maxn];
  84. int a[maxn], nex = 0;
  85. inline void dfs(int v){
  86. st[v] = nex;
  87. rep(x, tof[v])
  88. a[nex ++] = x;
  89. rep(u, adj[v])
  90. dfs(u);
  91. ft[v] = nex;
  92. }
  93. vi seg[maxn * 4];
  94. inline void segbuild(int id = 1,int l = 0,int r = nex){
  95. if(r - l < 2){
  96. seg[id].pb(a[l]);
  97. return ;
  98. }
  99. int mid = (l+r)/2;
  100. segbuild(L(id), l, mid);
  101. segbuild(R(id), mid, r);
  102. merge(all(seg[L(id)]), all(seg[R(id)]), back_inserter(seg[id]));
  103. }
  104. inline int ask(int x, int y, int a,int b,int id = 1,int l = 0,int r = nex){
  105. if(l >= y or x >= r)
  106. return 0;
  107. if(x <= l && r <= y)
  108. return upper_bound(all(seg[id]), b) - upper_bound(all(seg[id]), a-1);
  109. int mid = (l+r)/2;
  110. return ask(x, y, a, b, L(id), l, mid) +
  111. ask(x, y, a, b, R(id), mid, r) ;
  112. }
  113. char ch[maxn];
  114. int main(){
  115. memset(TRIE, -1, sizeof TRIE);
  116. memset(par, -1, sizeof par);
  117. ver[0].pb(root);
  118. int n, q;
  119. scanf("%d %d", &n, &q);
  120. For(i,0,n){
  121. scanf("%s", ch);
  122. s[i] = (string)ch;
  123. build(i);
  124. }
  125. ahoc();
  126. For(i,0,n)
  127. go(i);
  128. For(i,1,nx){
  129. par[i] = f[i];
  130. adj[par[i]].pb(i);
  131. }
  132. dfs(root);
  133. segbuild();
  134. For(i,0,q){
  135. int l, r, k;
  136. scanf("%d %d %d", &l, &r, &k);
  137. -- l, -- k, -- r;
  138. k = ::end[k];
  139. printf("%d\n", ask(st[k], ft[k], l, r));
  140. }
  141. }
  142.  
  143.  
Runtime error #stdin #stdout 0.35s 161984KB
stdin
Standard input is empty
stdout
Standard output is empty