fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. using ll = long long;
  5.  
  6. const int MAXN = 4.1e5;
  7. int sa[MAXN];
  8. int inv_sa[MAXN];
  9. int longest[MAXN];
  10. int classes[MAXN];
  11. vector<int> indices[26];
  12. int buf[MAXN];
  13. int ptr[MAXN];
  14.  
  15. void gen_suffix_array(int n, const string& s) {
  16. 	for (int i = n-1; i >= 0; i--) {
  17. 		indices[s[i] - 'a'].push_back(i);
  18. 	}
  19. 	int cur = 0;
  20. 	for (int c = 0; c < 26; c++) {
  21. 		vector<int>& v = indices[c];
  22. 		for (int i = 0; i < (int)v.size(); i++) {
  23. 			sa[cur++] = v[i];
  24. 		}
  25. 	}
  26. 	for (int i = 0; i < n; i++) classes[i] = (int)s[i];
  27. 	for (int step = 1; step < n; step *= 2) {
  28. 		copy(classes, classes + n, buf);
  29. 		for (int i = 0; i < n; i++) {
  30. 			if (i > 0 && sa[i-1] + step < n 
  31. 				&& buf[sa[i-1]] == buf[sa[i]] 
  32. 				&& buf[sa[i-1] + step / 2] == buf[sa[i] + step / 2]) {
  33. 				classes[sa[i]] = classes[sa[i-1]];
  34. 			} else {
  35. 				classes[sa[i]] = i;
  36. 			}
  37. 		}
  38. 		for (int i = 0; i < n; i++) ptr[i] = i;
  39. 		copy(sa, sa + n, buf);
  40. 		for (int i = 0; i < n; i++) {
  41. 			int j = buf[i] - step;
  42. 			if (j >= 0) {
  43. 				sa[ptr[classes[j]]++] = j;
  44. 			}
  45. 		}
  46. 	}
  47.  
  48. 	for (int i = 0; i < n; i++) inv_sa[sa[i]] = i;
  49. 	cur = 0;
  50. 	for (int z = 0; z < n; z++) {
  51. 		int i = inv_sa[z];
  52. 		if (cur) cur--;
  53. 		if (i+1 < n) {
  54. 			while (max(sa[i], sa[i+1]) + cur < n && s[sa[i] + cur] == s[sa[i+1] + cur]) {
  55. 				cur++;
  56. 			}
  57. 			longest[i] = cur;
  58. 		}
  59. 	}
  60. }
  61.  
  62. const int L = 20;
  63. int sparse[L+1][MAXN];
  64.  
  65. int main() {
  66. 	ios::sync_with_stdio(0), cin.tie(0);
  67.  
  68. 	int n, qnum;
  69. 	cin >> n >> qnum;
  70. 	string s;
  71. 	cin >> s;
  72. 	gen_suffix_array(n, s);
  73. 	copy(longest, longest + (n-1), sparse[0]);
  74. 	for (int l = 0; l < L; l++) {
  75. 		int step = 1 << l;
  76. 		if (2 * step >= n) break;
  77. 		for (int i = 0; i + 2 * step < n; i++) {
  78. 			sparse[l + 1][i] = min(sparse[l][i], sparse[l][i + step]);
  79. 		}
  80. 	}
  81. 	auto longest_query = [&](int a, int b) -> int {
  82. 		if (a == b) return n - a;
  83. 		a = inv_sa[a];
  84. 		b = inv_sa[b];
  85. 		if (a > b) swap(a, b);
  86. 		int l = 31 - __builtin_clz(b - a);
  87. 		return min(sparse[l][a], sparse[l][b - (1 << l)]);
  88. 	};
  89. 	for (int _ = 0; _ < qnum; _++) {
  90. 		int snum, mod;
  91. 		cin >> snum >> mod;
  92. 		vector<pair<int, int>> substrings(snum);
  93. 		for (auto& z : substrings) {
  94. 			cin >> z.first >> z.second;
  95. 			z.first--;
  96. 			z.second -= z.first;
  97. 		}
  98. 		sort(substrings.begin(), substrings.end(), [&](const pair<int, int>& a, const pair<int, int>& b) {
  99. 			int val = longest_query(a.first, b.first);
  100. 			if (val >= min(a.second, b.second)) {
  101. 				// one is a prefix of the other
  102. 				return a.second < b.second;
  103. 			} else {
  104. 				return s[a.first + val] < s[b.first + val];
  105. 			}
  106. 		});
  107. 		vector<pair<int, int>> combine(snum - 1);
  108. 		for (int i = 0; i+1 < snum; i++) {
  109. 			auto& a = substrings[i];
  110. 			auto& b = substrings[i+1];
  111. 			int zz = min({longest_query(a.first, b.first), a.second, b.second});
  112. 			combine[i] = {zz, i};
  113. 		}
  114. 		sort(combine.begin(), combine.end());
  115. 		reverse(combine.begin(), combine.end());
  116. 		vector<int> par(snum, -1);
  117. 		vector<int> ans(snum, 2 % mod);
  118. 		function<int(int)> getpar = [&](int a) {
  119. 			return par[a] < 0 ? a : (par[a] = getpar(par[a]));
  120. 		};
  121. 		for (auto z : combine) {
  122. 			int a = getpar(z.second);
  123. 			int b = getpar(z.second + 1);
  124. 			ll num_ways;
  125. 			if (-par[a] == 1 && substrings[a].second == z.first) {
  126. 				num_ways = (1 + ans[b]) % mod;
  127. 			} else {
  128. 				num_ways = ll(ans[a]) * ans[b] % mod;
  129. 			}
  130. 			if (-par[a] < -par[b]) swap(a, b);
  131. 			par[a] += par[b];
  132. 			par[b] = a;
  133. 			ans[a] = num_ways;
  134. 		}
  135. 		cout << ans[getpar(0)] << '\n';
  136. 	}
  137.  
  138. 	return 0;
  139. }
  140.  
Success #stdin #stdout 0s 4336KB
comments (?)
stdin
copy 
10 6
aabbaacaba
4 30 1 2 5 6 10 10 10 10
5 20 1 2 3 4 5 6 7 8 9 10
1 2 1 10
3 20 9 9 7 7 8 8
5 20 6 6 7 7 8 8 9 9 10 10
4 20 1 1 2 2 3 3 4 4
stdout
copy 
5
4
0
8
16
9
https://ideone.com/NlC7lB
language:
C++14 (gcc 8.3)
created:
5 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!