fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. #define ld long double
  4. #define pii pair <int, int>
  5. #define pll pair <ll, ll>
  6. #define pci pair <char, int>
  7. #define pld pair <ld, ld>
  8. #define pb push_back
  9. #define eb emplace_back
  10. #define mp make_pair
  11. #define fi first
  12. #define se second
  13. #define cd complex <double>
  14. #define PI 3.14159265358979
  15. using namespace std;
  16. mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
  17. int jump_l[200005][25], jump_r[200005][25];
  18. ll sum_l[200005][25], sum_r[200005][25];
  19. int n;
  20. string s;
  21. int l[200005], r[200005], cnt_cir[200005], max_l[200005], min_r[200005]; 
  22. int prefix[200005][27], suffix[200005][27];
  23. int locc[200005][27], rocc[200005][27], last[30];
  24. int cnt_cp[200005], cnt_cs[200005];
  25. pii last_suff[200005][27], last_pref[200005][27];
  26. bool comp(pii a, pii b){
  27. 	return a > b;
  28. }
  29. int main(){
  30. 	ios_base::sync_with_stdio(0);
  31. 	cin.tie(0); cout.tie(0);
  32. 	cin >> s; n = s.length();
  33. 	ll rnd = 0; rnd++;
  34. 	for (int i = 1; i <= n; i++){
  35. 		for (int c = 1; c <= 26; c++){
  36. 			locc[i][c] = last[c];
  37. 			prefix[i][c] = prefix[i - 1][c];
  38. 		}
  39. 		last[s[i - 1] - 'a' + 1] = i;
  40. 		for (int c = 1; c <= 26; c++) last_pref[i][c] = mp(last[c], c);
  41. 		sort(last_pref[i] + 1, last_pref[i] + 27, comp);
  42. 		prefix[i][s[i - 1] - 'a' + 1]++;
  43. 		for (int c = 1; c <= 26; c++) cnt_cp[i] += (prefix[i][c] != 0);
  44. 		l[i] = r[i] = i;
  45. 	}
  46. 	for (int c = 1; c <= 26; c++) last[c] = n + 1;
  47. 	for (int i = n; i >= 1; i--){
  48. 		for (int c = 1; c <= 26; c++){
  49. 			rocc[i][c] = last[c];
  50. 			suffix[i][c] = suffix[i + 1][c];
  51. 		}
  52. 		last[s[i - 1] - 'a' + 1] = i;
  53. 		for (int c = 1; c <= 26; c++) last_suff[i][c] = mp(last[c], c);
  54. 		sort(last_suff[i] + 1, last_suff[i] + 27);
  55. 		suffix[i][s[i - 1] - 'a' + 1]++;
  56. 		for (int c = 1; c <= 26; c++) cnt_cs[i] += (suffix[i][c] != 0);
  57. 	}
  58. 	ll ans = 0;
  59. 	for (int i = 1; i <= n; i++){
  60. 		jump_l[i][0] = n + 1;
  61. 		cnt_cir[i] = 0; max_l[i] = 0; min_r[i] = n + 1;
  62. 		for (int c = 1; c <= 26; c++){
  63. 			if (prefix[r[i]][c] - prefix[l[i] - 1][c]) cnt_cir[i]++;
  64. 			else{
  65. 				max_l[i] = max(max_l[i], locc[i][c]);
  66. 				min_r[i] = min(min_r[i], rocc[i][c]);
  67. 			}
  68. 		}
  69. 	}
  70. 	for (int cnt_c = 1; cnt_c <= cnt_cp[n]; cnt_c++){
  71. 		for (int i = 1; i <= n; i++){
  72. 			sum_r[i][0] = sum_l[i][0] = i;
  73. 			if (cnt_cp[i] >= cnt_c) jump_r[i][0] = max(jump_r[i][0], rocc[i][last_pref[i][cnt_c].se]);
  74. 			if (jump_r[i][0] == n + 1) jump_r[i][0] = n;
  75. 			if (cnt_cs[i] >= cnt_c) jump_l[i][0] = min(jump_l[i][0], locc[i][last_suff[i][cnt_c].se]);
  76. 			if (jump_l[i][0] == 0) jump_l[i][0] = 1;
  77. 		}
  78. 		for (int lay = 1; lay <= 17; lay++){
  79. 			for (int i = 1; i <= n; i++){
  80. 				if (jump_l[i][lay - 1] == 0) jump_l[i][lay] = 0; 
  81. 				else{
  82. 					sum_l[i][lay] = sum_l[i][lay - 1] + sum_l[jump_l[i][lay - 1]][lay - 1];
  83. 					jump_l[i][lay] = jump_l[jump_l[i][lay - 1]][lay - 1];
  84. 				}
  85. 				if (jump_r[i][lay - 1] == n + 1) jump_r[i][lay] = n + 1;
  86. 				else{
  87. 					sum_r[i][lay] = sum_r[i][lay - 1] + sum_r[jump_r[i][lay - 1]][lay - 1];
  88. 					jump_r[i][lay] = jump_r[jump_r[i][lay - 1]][lay - 1];
  89. 				}	
  90. 			}
  91. 		}
  92. 		for (int i = 1; i <= n; i++){
  93. 			if ((l[i] == 1) && (r[i] == n)) continue;
  94. 			if (cnt_cir[i] > cnt_c) continue;
  95. 			int cur_l = l[i], cur_r = r[i];
  96. 			for (int bit = 17; bit >= 0; bit--){
  97. 				if ((jump_r[cur_r][bit] >= min_r[i]) || (jump_l[cur_l][bit] <= max_l[i])) continue;
  98. 				ans -= sum_r[cur_r][bit]; ans += sum_l[cur_l][bit];
  99. 				ans += ((ll) (n - 1) << bit);
  100. 				cur_l = jump_l[cur_l][bit]; cur_r = jump_r[cur_r][bit]; 
  101. 			}
  102. 			ans += cur_l; ans -= cur_r; ans += (n - 1);
  103. 			l[i] = jump_l[cur_l][0]; r[i] = jump_r[cur_r][0];
  104. 			cnt_cir[i] = 0; max_l[i] = 0; min_r[i] = n + 1;
  105. 			for (int c = 1; c <= 26; c++){
  106. 				if (prefix[r[i]][c] - prefix[l[i] - 1][c]) cnt_cir[i]++;
  107. 				else{
  108. 					max_l[i] = max(max_l[i], locc[i][c]);
  109. 					min_r[i] = min(min_r[i], rocc[i][c]);
  110. 				}
  111. 			}
  112. 		}
  113. 	}
  114. 	cout << ans << "\n";
  115. }
Success #stdin #stdout 0.01s 7804KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/7lHwIB
language:
C++14 (gcc 8.3)
created:
3 years ago
visibility:
secret

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!