fork download
copy 
  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 = 1e5 + 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. vi ends[maxn];
  40. inline void build(int x){
  41. 	int v = root;
  42. 	rep(ch, s[x]){
  43. 		int c = ch - 'a';
  44. 		if(TRIE[v][c] == -1){
  45. 			TRIE[v][c] = nx;
  46. 			++ nx;
  47. 		}
  48. 		v = TRIE[v][c];
  49. 	}
  50. 	::end[x] = v;
  51. 	::ends[v].pb(x);
  52. }
  53. inline void ahoc(){
  54. 	f[root] = root;
  55. 	queue<int> q;
  56. 	q.push(root);
  57. 	while(!q.empty()){
  58. 		int v = q.front();
  59. 		q.pop();
  60. 		For(c,0,26){
  61. 			if(TRIE[v][c] != -1){
  62. 				aut[v][c] = TRIE[v][c];	
  63. 				if(v != root)
  64. 					f[aut[v][c]] = aut[f[v]][c];
  65. 				else
  66. 					f[aut[v][c]] = root;
  67. 				q.push(TRIE[v][c]);
  68. 			}
  69. 			else{
  70. 				if(v == root)
  71. 					aut[v][c] = root;
  72. 				else
  73. 					aut[v][c] = aut[f[v]][c];
  74. 			}
  75. 		}
  76. 	}
  77. }
  78. inline void go(int x){
  79. 	int v = root;
  80. 	rep(ch, s[x]){
  81. 		int c = ch - 'a';
  82. 		v = aut[v][c];
  83. 		tof[v].pb(x);
  84. 	}
  85. }
  86. int par[maxn];
  87. char ch[maxn];
  88. const int K = 350;
  89. struct sqrt_decomposition{
  90. 	ll sum[maxn] = {}, tot[K] = {};
  91. 	inline void add(int p, ll val){
  92. 		while(p < maxn && p % K)
  93. 			sum[p ++] += val;
  94. 		while(p < maxn){
  95. 			tot[p/K] += val;
  96. 			p += K;
  97. 		}
  98. 	}
  99. 	inline ll ask(int p){
  100. 		return (p < 0 ? 0 : sum[p] + tot[p/K]);
  101. 	}
  102. }SQRT;
  103. struct query{
  104. 	int l, r, k;
  105. 	ll ans = 0LL;
  106. 	query(){}
  107. 	query(int L, int R, int K){
  108. 		l = L;
  109. 		r = R;
  110. 		k = K;
  111. 	}
  112. }Q[maxn];
  113. vi queries[maxn];
  114. inline void dfs(int v){
  115. 	rep(a, ::ends[v])
  116. 		SQRT.add(a, 1);
  117. 	rep(i, tof[v])	if((int)s[i].size() < K){
  118. 		rep(j, queries[i])
  119. 			Q[j].ans += SQRT.ask(Q[j].r) - SQRT.ask(Q[j].l - 1);
  120. 	}
  121. 	rep(u, adj[v])	dfs(u);
  122. 	rep(a, ::ends[v])
  123. 		SQRT.add(a, -1);
  124. }
  125. ll ps[maxn];
  126. inline int dfs(int v, int x){
  127. 	int cnt = 0;
  128. 	rep(a, tof[v])	if(a == x)
  129. 		++ cnt;
  130. 	rep(u, adj[v])
  131. 		cnt += dfs(u, x);
  132. 	rep(a, ::ends[v])
  133. 		ps[a] += (ll)cnt;
  134. 	return cnt;
  135. }
  136. int main(){
  137. 	memset(TRIE, -1, sizeof TRIE);
  138. 	memset(par, -1, sizeof par);
  139. 	int n, q;
  140. 	scanf("%d %d", &n, &q);
  141. 	For(i,0,n){
  142. 		scanf("%s", ch);
  143. 		s[i] = (string)ch;
  144. 		build(i);
  145. 	}
  146. 	ahoc();
  147. 	For(i,0,n)
  148. 		go(i);
  149. 	For(i,1,nx){
  150. 		par[i] = f[i];
  151. 		adj[par[i]].pb(i);
  152. 	}
  153. 	For(i,0,q){
  154. 		int l, r, k;
  155. 		scanf("%d %d %d", &l, &r, &k);
  156. 		-- l, -- r, -- k;
  157. 		Q[i] = query(l, r, k);
  158. 		queries[k].pb(i);
  159. 	}
  160. 	For(i,0,n)	if((int)s[i].size() >= K){
  161. 		fill(ps, ps + maxn, 0LL);
  162. 		dfs(root, i);
  163. 		For(i,1,maxn)
  164. 			ps[i] += ps[i-1];
  165. 		rep(j, queries[i])
  166. 			Q[j].ans += ps[Q[j].r] - (Q[j].l ? ps[Q[j].l-1] : 0LL);
  167. 	}
  168. 	dfs(root);
  169. 	For(i,0,q)
  170. 		printf("%lld\n", Q[i].ans);
  171. 	return 0;
  172. }
  173.  
  174.  
Runtime error #stdin #stdout 0.07s 34152KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/kIQjcI
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!