概要

各質問 \([L, R]\) について、その中に含まれる連続区間のうち、白黒を交互に並べ替えられる区間の個数を求めます。

重要なのは、区間内の白石数と黒石数の差が \(1\) 以下なら交互に並べられる、という点です。

考察

区間に含まれる白石の数を \(W\)、黒石の数を \(B\) とします。

この区間の石を並べ替えて、隣り合う石の色が必ず異なるようにできる条件は、

\[ |W - B| \leq 1 \]

です。

例えば、

• WBWB のように白黒同数なら可能
• WBW のように片方が \(1\) 個だけ多い場合も可能
• WWWB のように差が \(2\) 以上あると、どう並べても同じ色が隣り合ってしまう

したがって、各区間について白石数と黒石数の差だけ分かればよいです。

ここで、文字列 \(S\) の各文字を次のように数値化します。

• W を \(+1\)
• B を \(-1\)

そして累積和を

\[ A_i = S_1 + S_2 + \cdots + S_i \]

とします。

ただし、\(A_0 = 0\) とします。

区間 \([l, r]\) における白石数と黒石数の差は、

\[ A_r - A_{l-1} \]

で求められます。

よって、区間 \([l, r]\) がよい区間である条件は、

\[ |A_r - A_{l-1}| \leq 1 \]

です。

---

質問 \([L, R]\) で数えたいのは、

\[ L \leq l \leq r \leq R \]

を満たす区間 \([l, r]\) です。

これは、累積和の添字で見ると、

\[ L-1 \leq i < j \leq R \]

を満たす組 \((i, j)\) に対応します。

つまり、各質問は

累積和列 \(A\) の区間 \([L-1, R]\) に含まれる要素のペア \((i, j)\) のうち、値の差が \(1\) 以下のものの個数を求める問題

に変換できます。

---

素朴に各質問ごとにすべての区間を調べると、最悪で \(O(N^2Q)\) かかり、制約 \(N, Q \leq 5 \times 10^4\) では間に合いません。

そこで、区間に対するペア数を高速に更新できる Mo’s algorithm を使います。

アルゴリズム

まず、累積和配列 \(A\) を作ります。

W -> +1
B -> -1

として、\(A_0, A_1, \dots, A_N\) を計算します。

質問 \([L, R]\) は、累積和配列上の区間

\[ [L-1, R] \]

に変換します。

この区間に含まれる累積和の値の集合について、値の差が \(0\) または \(1\) のペア数を数えれば答えです。

---

Mo’s algorithm では、現在見ている区間を少しずつ左右に伸ばしたり縮めたりしながら、各質問に答えます。

現在の区間に含まれる累積和の値の頻度を freq で管理します。

ある値 \(x\) を新しく追加するとき、その \(x\) とペアを作れる既存の値は

\[ x-1, x, x+1 \]

です。

したがって、追加によって増える答えは

\[ freq[x-1] + freq[x] + freq[x+1] \]

です。

その後、freq[x] を \(1\) 増やします。

削除するときは逆に、先に freq[x] を \(1\) 減らしてから、

\[ freq[x-1] + freq[x] + freq[x+1] \]

を答えから引きます。

---

例えば、現在の区間に累積和の値が

1, 2, 2, 4

とあるとします。

ここに \(x = 3\) を追加する場合、差が \(1\) 以下になる既存の値は

2, 2, 4

なので、新たに \(3\) 個のよいペアが増えます。

これは

\[ freq[2] + freq[3] + freq[4] \]

で求められます。

計算量

• 時間計算量: \(O((N + Q)\sqrt{N} + Q \log Q)\)
• 空間計算量: \(O(N + Q)\)

実装のポイント

累積和 \(A_i\) は負になる可能性があります。

そのまま配列の添字として使うことはできないので、コードでは offset = N + 2 を足して、すべて正の値になるようにしています。

A[0] = offset;

とし、その後に +1 または -1 を加えて累積和を作っています。

また、質問 \([L, R]\) は累積和上では \([L-1, R]\) になるため、入力された \(L\) から \(1\) を引いて保存しています。

queries[i] = {L - 1, R, i};

答えはペア数なので、最大で \(O(N^2)\) になる可能性があります。

そのため、int ではなく long long を使う必要があります。

ソースコード

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

struct Query {
    int l, r, idx;
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, Q;
    cin >> N >> Q;

    string S;
    cin >> S;

    int M = N + 1;
    int offset = N + 2;

    vector<int> A(M);
    A[0] = offset;
    for (int i = 1; i <= N; i++) {
        int v = (S[i - 1] == 'W') ? 1 : -1;
        A[i] = A[i - 1] + v;
    }

    vector<Query> queries(Q);
    for (int i = 0; i < Q; i++) {
        int L, R;
        cin >> L >> R;
        queries[i] = {L - 1, R, i};
    }

    int block = max(1, (int)sqrt(M));

    sort(queries.begin(), queries.end(), [&](const Query& a, const Query& b) {
        int ab = a.l / block;
        int bb = b.l / block;
        if (ab != bb) return ab < bb;
        if (ab & 1) return a.r > b.r;
        return a.r < b.r;
    });

    vector<int> freq(2 * N + 10, 0);
    vector<long long> ans(Q);

    long long curAns = 0;
    int curL = 0, curR = -1;

    auto add = [&](int idx) {
        int x = A[idx];
        curAns += (long long)freq[x - 1] + freq[x] + freq[x + 1];
        freq[x]++;
    };

    auto remove = [&](int idx) {
        int x = A[idx];
        freq[x]--;
        curAns -= (long long)freq[x - 1] + freq[x] + freq[x + 1];
    };

    for (const auto& q : queries) {
        while (curL > q.l) add(--curL);
        while (curR < q.r) add(++curR);
        while (curL < q.l) remove(curL++);
        while (curR > q.r) remove(curR--);

        ans[q.idx] = curAns;
    }

    for (int i = 0; i < Q; i++) {
        cout << ans[i] << '\n';
    }

    return 0;
}

---

この解説は gpt-5.5-xhigh によって生成されました。