#include <bits/stdc++.h> using namespace std; #ifdef D #define DEBUG(x) \ do { \ x \ cout.flush(); \ } while (0) #else #define DEBUG(x) #endif using pii = pair<int, int>; pii operator+(const pii &a, const pii &b) { return {a.first + b.first, a.second + b.second}; } pii operator-(const pii &a, const pii &b) { return {a.first - b.first, a.second - b.second}; } pii charToPii(char c) { if (c == 'a') return {0, 2}; if (c == 'b') return {1, -1}; return {-1, -1}; } ostream& operator<<(ostream &os, const pii &p) { return os << "(" << p.first << " " << p.second << ")"; } const int MAXN = 3e5 + 7; string s; int pref2[MAXN]; int value[150]; pii pref3[MAXN]; map<int, int> mapa2; map<pii, int> mapa3; long long res; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cin >> s; mapa3[{0, 0}]++; for (int i = 1; i <= s.size(); i++) { pref3[i] = pref3[i - 1] + charToPii(s[i - 1]); res += mapa3[pref3[i]]; mapa3[pref3[i]]++; DEBUG(cout << res << " ";); } mapa2[0]++; value['b'] = 1; value['c'] = -1; for (int i = 1; i <= s.size(); i++) { if (s[i - 1] == 'a') { mapa2.clear(); mapa2[0]++; } else { pref2[i] = pref2[i - 1] + value[s[i - 1]]; res += mapa2[pref2[i]]; mapa2[pref2[i]]++; DEBUG(cout << res << " ";); } } memset(pref2, 0, (s.size() + 3) * sizeof (int)); mapa2.clear(); mapa2[0]++; value['a'] = 1; value['c'] = -1; for (int i = 1; i <= s.size(); i++) { if (s[i - 1] == 'b') { mapa2.clear(); mapa2[0]++; } else { pref2[i] = pref2[i - 1] + value[s[i - 1]]; res += mapa2[pref2[i]]; mapa2[pref2[i]]++; DEBUG(cout << res << " ";); } } memset(pref2, 0, (s.size() + 3) * sizeof (int)); mapa2.clear(); mapa2[0]++; value['a'] = 1; value['b'] = -1; for (int i = 1; i <= s.size(); i++) { if (s[i - 1] == 'c') { mapa2.clear(); mapa2[0]++; } else { pref2[i] = pref2[i - 1] + value[s[i - 1]]; res += mapa2[pref2[i]]; mapa2[pref2[i]]++; DEBUG(cout << res << " ";); } } long long l = 1; for (int i = 1; i < s.size(); i++) { if (s[i] == s[i - 1]) { l++; } else { res += l * (l + 1) / 2; l = 1; } } res += l * (l + 1) / 2; cout << res; DEBUG( cout << "\n"; for (auto& e : mapa3) { cout << e.first << " " << e.second << "\n"; } ); return 0; }
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 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 | #include <bits/stdc++.h> using namespace std; #ifdef D #define DEBUG(x) \ do { \ x \ cout.flush(); \ } while (0) #else #define DEBUG(x) #endif using pii = pair<int, int>; pii operator+(const pii &a, const pii &b) { return {a.first + b.first, a.second + b.second}; } pii operator-(const pii &a, const pii &b) { return {a.first - b.first, a.second - b.second}; } pii charToPii(char c) { if (c == 'a') return {0, 2}; if (c == 'b') return {1, -1}; return {-1, -1}; } ostream& operator<<(ostream &os, const pii &p) { return os << "(" << p.first << " " << p.second << ")"; } const int MAXN = 3e5 + 7; string s; int pref2[MAXN]; int value[150]; pii pref3[MAXN]; map<int, int> mapa2; map<pii, int> mapa3; long long res; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cin >> s; mapa3[{0, 0}]++; for (int i = 1; i <= s.size(); i++) { pref3[i] = pref3[i - 1] + charToPii(s[i - 1]); res += mapa3[pref3[i]]; mapa3[pref3[i]]++; DEBUG(cout << res << " ";); } mapa2[0]++; value['b'] = 1; value['c'] = -1; for (int i = 1; i <= s.size(); i++) { if (s[i - 1] == 'a') { mapa2.clear(); mapa2[0]++; } else { pref2[i] = pref2[i - 1] + value[s[i - 1]]; res += mapa2[pref2[i]]; mapa2[pref2[i]]++; DEBUG(cout << res << " ";); } } memset(pref2, 0, (s.size() + 3) * sizeof (int)); mapa2.clear(); mapa2[0]++; value['a'] = 1; value['c'] = -1; for (int i = 1; i <= s.size(); i++) { if (s[i - 1] == 'b') { mapa2.clear(); mapa2[0]++; } else { pref2[i] = pref2[i - 1] + value[s[i - 1]]; res += mapa2[pref2[i]]; mapa2[pref2[i]]++; DEBUG(cout << res << " ";); } } memset(pref2, 0, (s.size() + 3) * sizeof (int)); mapa2.clear(); mapa2[0]++; value['a'] = 1; value['b'] = -1; for (int i = 1; i <= s.size(); i++) { if (s[i - 1] == 'c') { mapa2.clear(); mapa2[0]++; } else { pref2[i] = pref2[i - 1] + value[s[i - 1]]; res += mapa2[pref2[i]]; mapa2[pref2[i]]++; DEBUG(cout << res << " ";); } } long long l = 1; for (int i = 1; i < s.size(); i++) { if (s[i] == s[i - 1]) { l++; } else { res += l * (l + 1) / 2; l = 1; } } res += l * (l + 1) / 2; cout << res; DEBUG( cout << "\n"; for (auto& e : mapa3) { cout << e.first << " " << e.second << "\n"; } ); return 0; } |