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. vi adj[maxn];
  38. int end[maxn];
  39. inline void build(int x){
  40. int v = root;
  41. rep(ch, s[x]){
  42. int c = ch - 'a';
  43. if(TRIE[v][c] == -1){
  44. TRIE[v][c] = nx;
  45. ++ nx;
  46. }
  47. v = TRIE[v][c];
  48. }
  49. ::end[x] = v;
  50. }
  51. inline void ahoc(){
  52. f[root] = root;
  53. queue<int> q;
  54. q.push(root);
  55. while(!q.empty()){
  56. int v = q.front();
  57. q.pop();
  58. 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. q.push(TRIE[v][c]);
  66. }
  67. else{
  68. if(v == root)
  69. aut[v][c] = root;
  70. else
  71. aut[v][c] = aut[f[v]][c];
  72. }
  73. }
  74. }
  75. }
  76. inline void go(int x){
  77. int v = root;
  78. rep(ch, s[x]){
  79. int c = ch - 'a';
  80. v = aut[v][c];
  81. tof[v].pb(x);
  82. }
  83. }
  84. int par[maxn];
  85. int st[maxn], ft[maxn];
  86. int a[maxn], nex = 0;
  87. inline void dfs(int v){
  88. st[v] = nex;
  89. rep(x, tof[v])
  90. a[nex ++] = x;
  91. rep(u, adj[v])
  92. dfs(u);
  93. ft[v] = nex;
  94. }
  95. struct query{
  96. int l, r, k, ind, sgn;
  97. query(){
  98. l = r = k = 0;
  99. }
  100. query(int L,int R,int K,int IND,int SGN){l = L, r = R, k = K, ind = IND, sgn = SGN;}
  101. bool operator < (const query &a) const{
  102. if(k != a.k)
  103. return k < a.k;
  104. return pii(l, r) < pii(a.l, a.r);
  105. }
  106. };
  107. pii p[maxn];
  108. int fen[maxn];
  109. inline void add(int x){
  110. ++ x;
  111. for(int i = x;i < maxn;i += i & -i)
  112. fen[i] ++;
  113. }
  114. inline int ask(int x){
  115. ++ x;
  116. int res = 0;
  117. for(int i = x;i > 0;i -= i & -i)
  118. res += fen[i];
  119. return res;
  120. }
  121. inline int ask(int l, int r){
  122. return max(0, ask(r) - ask(l-1));
  123. }
  124. int answ[maxn];
  125. vector<query> quer;
  126. int lq[maxn], rq[maxn], kq[maxn];
  127. char ch[maxn];
  128. int main(){
  129. memset(TRIE, -1, sizeof TRIE);
  130. memset(par, -1, sizeof par);
  131. int n, q;
  132. scanf("%d %d", &n, &q);
  133. For(i,0,n){
  134. scanf("%s", ch);
  135. s[i] = (string)ch;
  136. build(i);
  137. }
  138. ahoc();
  139. For(i,0,n)
  140. go(i);
  141. For(i,1,nx){
  142. par[i] = f[i];
  143. adj[par[i]].pb(i);
  144. }
  145. dfs(root);
  146. For(i,0,q){
  147. scanf("%d %d %d", lq + i, rq + i, kq + i);
  148. -- kq[i];
  149. kq[i] = ::end[kq[i]];
  150. lq[i] --;
  151. rq[i] --;
  152. quer.pb(query(st[kq[i]], ft[kq[i]] - 1, lq[i] - 1, i, -1));
  153. quer.pb(query(st[kq[i]], ft[kq[i]] - 1, rq[i], i, 1));
  154. }
  155. sort(all(quer));
  156. For(i,0,nex)
  157. p[i] = {a[i], i};
  158. sort(p, p + nex);
  159. int po = 0;
  160. rep(q, quer){
  161. int l = q.l;
  162. int r = q.r;
  163. int k = q.k;
  164. while(po < nex && p[po].x <= k){
  165. add(p[po].y);
  166. po ++;
  167. }
  168. int ans = ask(l, r);
  169. int ind = q.ind;
  170. answ[ind] += q.sgn * ans;
  171. }
  172. For(i,0,q)
  173. printf("%d\n", answ[i] );
  174. }
  175.  
  176.  
Runtime error #stdin #stdout 0.34s 144320KB
stdin
Standard input is empty
stdout
Standard output is empty