Submission #20387807

---

Source Code Expand

#include <bits/stdc++.h>
typedef long long lint;
using namespace std;

string s;

char seed(int x) {
    if (s[x] == s[x + 1] && s[x] != s[x + 2]) {
        return s[x];
    } else {
        return 'X';
    }
}

// 累積和
struct cumulative_sum {
    using lint = long long int;
    int sz;
    // data[i]:元の数列
    vector<lint> data;
    // cum[i]:[0,i)の和
    vector<lint> sum;
    // 要素数を指定して初期化
    cumulative_sum(const int _sz) : sz(_sz) {
        data.assign(sz, 0);
        sum.assign(sz + 1, 0);
    }
    lint& operator[](const int k) {
        return data[k];
    }
    // dataに基づいてsumを構築
    void build() {
        for (int i = 0; i < sz; i++) sum[i + 1] = sum[i] + data[i];
    }
    // [a,b)の和を求める
    lint query(const int a, const int b) {
        return sum[b] - sum[a];
    }
};

vector<cumulative_sum> counts() {
    lint n = s.length();
    vector<cumulative_sum> res(26, cumulative_sum(n));
    for (int i = 0; i < n; i++) {
        int c = s[i] - 'a';
        res[c][i] = 1;
    }
    for (int i = 0; i < 26; i++) {
        res[i].build();
    }
    return res;
}

int main() {
    cin >> s;
    int n = s.length();
    char before_c = 'Y';
    int before_i = n;
    lint ans = 0;
    auto cum = counts();
    for (int i = n - 3; i >= 0; i--) {
        char c = seed(i);
        if (c == 'X') {
            continue;
        }
        if (c != before_c) {
            ans += n - (i + 2) - cum[c - 'a'].query(i + 2, before_i);
        } else {
            ans += before_i - (i + 2) - cum[c - 'a'].query(i + 2, before_i);
        }
        before_c = c;
        before_i = i;
    }
    cout << ans << endl;
}

Submission Info

Judge Result