#include <bits/stdc++.h> using namespace std; constexpr int MAXLEN = 300000; constexpr int LETTERS = 3; uint64_t total = 0; int n; vector<int> c[LETTERS]; vector<int> d[LETTERS]; void MakeC() { vector<char> s(MAXLEN + 8); fgets(&s[0], MAXLEN + 1, stdin); s.resize(strlen(&s[0])); while (!s.empty() && !isalpha(s.back())) s.pop_back(); n = s.size(); for (int i = 0; i < 3; ++i) { c[i].resize(n + 1); c[i][0] = 0; } for (int j = 0; j < LETTERS; ++j) for (int i = 0; i < n; ++i) c[j][i + 1] = c[j][i] + ((s[i] - 'a') == j); } void MakeD() { for (int i = 0; i < 3; ++i) { d[i].resize(n + 1); int j = (i + 1) % 3; for (int k = 0; k <= n; ++k) d[i][k] = c[j][k] - c[i][k]; } } struct Bucket { const vector<int>& next; int i; void operator++() { i = next[i]; } bool operator!=(const Bucket& o) const { return i != o.i; } int operator*() const { return i; } Bucket begin() { return *this; } Bucket end() { return Bucket{next, -1}; } }; struct BucketMap { vector<int> first, next; BucketMap() { first.resize(2 * n + 1, -1); next.resize(n + 1, -1); } bool HasKey(int v) const { return first[v] >= 0; } void Add(int i, int v) { next[i] = first[v]; first[v] = i; } void Del(int i, int v) { first[v] = next[i]; next[i] = -1; } struct Iterator { const BucketMap& m; int i; void Shift() { while(i < (int) m.first.size() && m.first[i] < 0) ++i; } void operator++() { ++i; Shift(); } bool operator!=(const Iterator& o) const { return i != o.i; } int operator*() const { return i; } }; Iterator begin() { Iterator it{*this, 0}; it.Shift(); return it; } Iterator end() { return Iterator{*this, (int) first.size()}; } Bucket operator[](int v) const { return Bucket{next, first[v]}; } }; void Count(const vector<int>& a, const vector<int>& b) { BucketMap am, bm; for (int i = 0; i < (int) a.size(); ++i) am.Add(i, a[i] + n); vector<int> vals; vals.reserve(2 * n + 1); for (int v : am) { for (int i : am[v]) { int u = b[i] + n; if (!bm.HasKey(u)) vals.push_back(u); bm.Add(i, u); } for (int u : vals) { int size = 0; for (;;) { int j = *bm[u]; if (j < 0) break; size++; bm.Del(j, u); } total += uint64_t(size) * (size - 1) / 2; } vals.clear(); } } int main() { MakeC(); MakeD(); for (int i = 0; i < 3; ++i) { int j = (i + 1) % 3; Count(c[i], c[j]); Count(c[i], d[j]); } Count(d[0], d[1]); printf("%lu\n", total); 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 | #include <bits/stdc++.h> using namespace std; constexpr int MAXLEN = 300000; constexpr int LETTERS = 3; uint64_t total = 0; int n; vector<int> c[LETTERS]; vector<int> d[LETTERS]; void MakeC() { vector<char> s(MAXLEN + 8); fgets(&s[0], MAXLEN + 1, stdin); s.resize(strlen(&s[0])); while (!s.empty() && !isalpha(s.back())) s.pop_back(); n = s.size(); for (int i = 0; i < 3; ++i) { c[i].resize(n + 1); c[i][0] = 0; } for (int j = 0; j < LETTERS; ++j) for (int i = 0; i < n; ++i) c[j][i + 1] = c[j][i] + ((s[i] - 'a') == j); } void MakeD() { for (int i = 0; i < 3; ++i) { d[i].resize(n + 1); int j = (i + 1) % 3; for (int k = 0; k <= n; ++k) d[i][k] = c[j][k] - c[i][k]; } } struct Bucket { const vector<int>& next; int i; void operator++() { i = next[i]; } bool operator!=(const Bucket& o) const { return i != o.i; } int operator*() const { return i; } Bucket begin() { return *this; } Bucket end() { return Bucket{next, -1}; } }; struct BucketMap { vector<int> first, next; BucketMap() { first.resize(2 * n + 1, -1); next.resize(n + 1, -1); } bool HasKey(int v) const { return first[v] >= 0; } void Add(int i, int v) { next[i] = first[v]; first[v] = i; } void Del(int i, int v) { first[v] = next[i]; next[i] = -1; } struct Iterator { const BucketMap& m; int i; void Shift() { while(i < (int) m.first.size() && m.first[i] < 0) ++i; } void operator++() { ++i; Shift(); } bool operator!=(const Iterator& o) const { return i != o.i; } int operator*() const { return i; } }; Iterator begin() { Iterator it{*this, 0}; it.Shift(); return it; } Iterator end() { return Iterator{*this, (int) first.size()}; } Bucket operator[](int v) const { return Bucket{next, first[v]}; } }; void Count(const vector<int>& a, const vector<int>& b) { BucketMap am, bm; for (int i = 0; i < (int) a.size(); ++i) am.Add(i, a[i] + n); vector<int> vals; vals.reserve(2 * n + 1); for (int v : am) { for (int i : am[v]) { int u = b[i] + n; if (!bm.HasKey(u)) vals.push_back(u); bm.Add(i, u); } for (int u : vals) { int size = 0; for (;;) { int j = *bm[u]; if (j < 0) break; size++; bm.Del(j, u); } total += uint64_t(size) * (size - 1) / 2; } vals.clear(); } } int main() { MakeC(); MakeD(); for (int i = 0; i < 3; ++i) { int j = (i + 1) % 3; Count(c[i], c[j]); Count(c[i], d[j]); } Count(d[0], d[1]); printf("%lu\n", total); return 0; } |