概要

白黒の石の列から、並べ替えて交互に配置できる「よい区間」を定義し、各クエリで指定された範囲内のよい区間の個数を数える問題。累積和による条件の言い換えと Mo’s algorithm を組み合わせて効率的に解く。

考察

よい区間の条件を整理する

区間 \([l, r]\) に含まれる白石の個数を \(w\)、黒石の個数を \(b\) とする。これらを交互に並べるには、多い方の色が少ない方の色より 高々1個多い 必要がある。つまり：

\[|w - b| \leq 1\]

累積和で言い換える

白を \(+1\)、黒を \(-1\) とした累積和 \(p\) を定義する：

\[p[0] = 0, \quad p[i] = p[i-1] + \begin{cases} +1 & (S_i = \text{W}) \\ -1 & (S_i = \text{B}) \end{cases}\]

すると区間 \([l, r]\) での白黒の差は \(p[r] - p[l-1]\) となるので、よい区間の条件は：

\[|p[r] - p[l-1]| \leq 1\]

ペア数え上げ問題に帰着

クエリ \((L, R)\) に対し、\(L \leq l \leq r \leq R\) なるよい区間を数えることは、累積和配列の添字 \(a = l-1\), \(b = r\) に着目すると：

配列 \(p\) の添字 \(L-1\) から \(R\) の範囲で、\(a < b\) かつ \(|p[a] - p[b]| \leq 1\) を満たすペア \((a, b)\) の個数を求める

という問題に帰着される。

素朴な方法の問題点

各クエリごとに全ペアを調べると \(O((R - L)^2)\) で、最悪 \(O(N^2 Q)\) となり間に合わない。

アルゴリズム

Mo’s algorithm

区間に対するクエリを効率的に処理するオフラインアルゴリズム Mo’s algorithm を使う。

1. 前処理: クエリ \((L_i, R_i)\) を累積和配列上のクエリ \((L_i - 1, R_i)\) に変換する。
2. クエリのソート: 左端をブロックサイズ \(\sqrt{N}\) ごとにまとめ、同じブロック内では右端でソートする。
3. 区間の伸縮: 現在の区間 \([\text{cl}, \text{cr}]\) を1つずつ伸縮させながら、各クエリに答える。

add / remove の処理

値 \(v = p[\text{idx}]\) を持つ要素を追加する際、既に区間内にある要素との新しい「よいペア」の数は：

\[\text{freq}[v] + \text{freq}[v-1] + \text{freq}[v+1]\]

• \(\text{freq}[v]\): 差が \(0\) のペア
• \(\text{freq}[v-1]\), \(\text{freq}[v+1]\): 差が \(\pm 1\) のペア

追加後に \(\text{freq}[v]\) をインクリメントする。削除は逆順に行う。

具体例

\(S = \text{BWW}\) のとき、\(p = [0, -1, 0, 1]\)。

区間 \([1, 3]\) のクエリでは、添字 \(\{0, 1, 2, 3\}\) の \(p\) の値 \(\{0, -1, 0, 1\}\) から \(|p[a] - p[b]| \leq 1\) のペアを数える：

ペア \((a,b)\)	\(p[a], p[b]\)	差の絶対値	よい？
\((0,1)\)	\(0, -1\)	\(1\)	✓
\((0,2)\)	\(0, 0\)	\(0\)	✓
\((0,3)\)	\(0, 1\)	\(1\)	✓
\((1,2)\)	\(-1, 0\)	\(1\)	✓
\((1,3)\)	\(-1, 1\)	\(2\)	✗
\((2,3)\)	\(0, 1\)	\(1\)	✓

よい区間は 5 個。

計算量

• 時間計算量: \(O((N + Q) \sqrt{N})\)
  • Mo’s algorithm の区間伸縮回数が \(O((N + Q)\sqrt{N})\)、各伸縮は \(O(1)\)
• 空間計算量: \(O(N + Q)\)
  • 累積和配列、頻度配列、クエリ・回答の格納

実装のポイント

• 累積和の値域シフト: \(p[i]\) は \([-N, N]\) の範囲を取りうるため、頻度配列のインデックスとして p[idx] + N を使い、非負にシフトしている。

• add と remove の順序: Mo’s algorithm では、区間を広げる操作（add）を先に、狭める操作（remove）を後にする順序が重要。これにより区間が空になることを防ぐ。

• Mo’s algorithm のソート最適化: 偶数ブロックでは右端昇順、奇数ブロックでは右端降順にソートする（zigzag 方式）ことで、右端の移動量を削減している。

  ソースコード

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

int main(){
    int N, Q;
    scanf("%d%d", &N, &Q);
    char S[50001];
    scanf("%s", S);
    
    vector<int> p(N+1);
    p[0] = 0;
    for(int i = 0; i < N; i++){
        p[i+1] = p[i] + (S[i] == 'W' ? 1 : -1);
    }
    
    int block = max(1, (int)sqrt(N+1));
    
    struct Query {
        int l, r, idx;
    };
    
    vector<Query> queries(Q);
    for(int i = 0; i < Q; i++){
        int L, R;
        scanf("%d%d", &L, &R);
        queries[i] = {L-1, R, i};
    }
    
    sort(queries.begin(), queries.end(), [&](const Query& a, const Query& b){
        int ba = a.l / block, bb = b.l / block;
        if(ba != bb) return ba < bb;
        return (ba & 1) ? (a.r > b.r) : (a.r < b.r);
    });
    
    vector<long long> ans(Q);
    vector<int> freq(2*N+2, 0);
    long long cur = 0;
    int cl = 0, cr = -1;
    
    auto add = [&](int idx) {
        int v = p[idx] + N;
        cur += freq[v];
        if(v > 0) cur += freq[v-1];
        if(v < 2*N) cur += freq[v+1];
        freq[v]++;
    };
    
    auto rem = [&](int idx) {
        int v = p[idx] + N;
        freq[v]--;
        cur -= freq[v];
        if(v > 0) cur -= freq[v-1];
        if(v < 2*N) cur -= freq[v+1];
    };
    
    for(auto& q : queries){
        while(cr < q.r) add(++cr);
        while(cl > q.l) add(--cl);
        while(cr > q.r) rem(cr--);
        while(cl < q.l) rem(cl++);
        ans[q.idx] = cur;
    }
    
    for(int i = 0; i < Q; i++){
        printf("%lld\n", ans[i]);
    }
    
    return 0;
}

---

この解説は claude4.6opus-thinking によって生成されました。