#include <bits/stdc++.h> using namespace std; struct T { int a, b, c; bool operator<(const T &t) const { if(a != t.a) return a < t.a; if(b != t.b) return b < t.b; return c < t.c; } }; long long fn(string& s, int a, int b) { if(a == b) { // printf("%d %d 1\n", a, b); return 1; } if(a + 1 == b) { // printf("%d %d 3\n", a, b); return 3; } int m = (a + b) / 2; long long ans = fn(s, a, m) + fn(s, m + 1, b); int ma = 0, mb = 0, mc = 0; map<T, int> mab; map<T, int> mac; map<T, int> mbc; map<T, int> mabc; int ca = 0, cb = 0, cc = 0; for(int i = m; i >= a; i--) { if(s[i] == 'a') ca++; else if(s[i] == 'b') cb++; else cc++; if(ca == 0 && cb == 0) mc++; if(ca == 0 && cc == 0) mb++; if(cb == 0 && cc == 0) ma++; if(ca == 0) { int db = cb, dc = cc; while(db > 0 && dc > 0) db--, dc--; mbc[{0, db, dc}]++; } if(cb == 0) { int da = ca, dc = cc; while(da > 0 && dc > 0) da--, dc--; mac[{da, 0, dc}]++; } if(cc == 0) { int da = ca, db = cb; while(da > 0 && db > 0) da--, db--; mab[{da, db, 0}]++; } int da = ca, db = cb, dc = cc; while(da > 0 && db > 0 && dc > 0) da--, db--, dc--; mabc[{da, db, dc}]++; } ca = 0, cb = 0, cc = 0; for(int i = m+1; i <= b; i++) { if(s[i] == 'a') ca++; else if(s[i] == 'b') cb++; else cc++; if(ca == 0 && cb == 0) ans += mc; if(ca == 0 && cc == 0) ans += mb; if(cb == 0 && cc == 0) ans += ma; if(ca == 0) { int dm = max(cb, cc); ans += mbc[{0, dm-cb, dm-cc}]; } if(cb == 0) { int dm = max(ca, cc); ans += mac[{dm-ca, 0, dm-cc}]; } if(cc == 0) { int dm = max(ca, cb); ans += mab[{dm-ca, dm-cb, 0}]; } int dm = max(max(ca, cb), cc); ans += mabc[{dm-ca, dm-cb, dm-cc}]; } // printf("%d %d %lld\n", a, b, ans); return ans; } int main() { ios_base::sync_with_stdio(0); cin.tie(); string s; cin >> s; cout << fn(s, 0, s.size()-1) << "\n"; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 | #include <bits/stdc++.h> using namespace std; struct T { int a, b, c; bool operator<(const T &t) const { if(a != t.a) return a < t.a; if(b != t.b) return b < t.b; return c < t.c; } }; long long fn(string& s, int a, int b) { if(a == b) { // printf("%d %d 1\n", a, b); return 1; } if(a + 1 == b) { // printf("%d %d 3\n", a, b); return 3; } int m = (a + b) / 2; long long ans = fn(s, a, m) + fn(s, m + 1, b); int ma = 0, mb = 0, mc = 0; map<T, int> mab; map<T, int> mac; map<T, int> mbc; map<T, int> mabc; int ca = 0, cb = 0, cc = 0; for(int i = m; i >= a; i--) { if(s[i] == 'a') ca++; else if(s[i] == 'b') cb++; else cc++; if(ca == 0 && cb == 0) mc++; if(ca == 0 && cc == 0) mb++; if(cb == 0 && cc == 0) ma++; if(ca == 0) { int db = cb, dc = cc; while(db > 0 && dc > 0) db--, dc--; mbc[{0, db, dc}]++; } if(cb == 0) { int da = ca, dc = cc; while(da > 0 && dc > 0) da--, dc--; mac[{da, 0, dc}]++; } if(cc == 0) { int da = ca, db = cb; while(da > 0 && db > 0) da--, db--; mab[{da, db, 0}]++; } int da = ca, db = cb, dc = cc; while(da > 0 && db > 0 && dc > 0) da--, db--, dc--; mabc[{da, db, dc}]++; } ca = 0, cb = 0, cc = 0; for(int i = m+1; i <= b; i++) { if(s[i] == 'a') ca++; else if(s[i] == 'b') cb++; else cc++; if(ca == 0 && cb == 0) ans += mc; if(ca == 0 && cc == 0) ans += mb; if(cb == 0 && cc == 0) ans += ma; if(ca == 0) { int dm = max(cb, cc); ans += mbc[{0, dm-cb, dm-cc}]; } if(cb == 0) { int dm = max(ca, cc); ans += mac[{dm-ca, 0, dm-cc}]; } if(cc == 0) { int dm = max(ca, cb); ans += mab[{dm-ca, dm-cb, 0}]; } int dm = max(max(ca, cb), cc); ans += mabc[{dm-ca, dm-cb, dm-cc}]; } // printf("%d %d %lld\n", a, b, ans); return ans; } int main() { ios_base::sync_with_stdio(0); cin.tie(); string s; cin >> s; cout << fn(s, 0, s.size()-1) << "\n"; } |