ある連続する区間 \([l,r]\) がよい区間となる条件を考えます。 この区間にある W の数を \(w\) 、 B の数を \(b\) とすると、 条件は \(|w-b| \leq 1\) となることがわかります。

これを言い換えます。 \(C_0=0\) 、 \(C_i= ([1,i]\) にある W の個数 - B の個数 \()\) と定義します。この時、区間 \([l,r]\) がよい区間となる条件は \(|C_r-C_{l-1}| \leq 1\) です。

クエリはつまりは、 \(L_i-1 \leq l < r \leq R_i\) かつ \(|C_r-C_l| \leq 1\) を満たす \((l,r)\) の個数です。

各クエリは \(\mathrm{O}(R_i-L_i)\) で求めることができます。 \(l\) を固定した時によい区間の \(C_r\) が取りうる値が\(3\) 通りしかないことを利用します。 \(l\) の降順に行って行き \(C_r=x\) となる \(r\) の個数を \(x\) ごとに常に連想配列で持つことで \(l\) を固定した時のよい区間となる \(r\) が容易に求められるようになるからです。

この発想を応用して区間に関するクエリを答えるテクニックの一つである Mo’s Algorithm に適用することを考えます。Mo’s Algorithm 自体については ABC448 - F の解説 を参照してください。

先ほどの各クエリを \(\mathrm{O}(R_i-L_i)\) で計算する手法をそのまま利用できます。 現在の区間が \([l,r]\) と表せる時、連想配列で \(x\) ごとに \(C_i=x\) となる \(i (l \leq i \leq r)\) の個数を持っておき、 \(r+1\) を区間に追加する、 \(l-1\) を区間に追加するときにこの配列を参照して新たに増えるよい区間の左端あるいは右端が今追加した要素になる場合を考えてよい区間の個数に加算します。同様にして削除も行えます。

よって、時間計算量 \(\mathrm{O}((N+Q)\sqrt{N}+Q \log Q)\) でこの問題を解くことができます。

実装例(C++)

#include <bits/stdc++.h>
using namespace std;
struct Mo {
    int n;
    vector<int> left, right;
    Mo(int n) : n(n) {}
    void add(int l, int r) {
        left.push_back(l);
        right.push_back(r);
    }
    template <typename A, typename D, typename REM>
    void run(const A& add, const D& del, const REM& rem) {
        const int q = left.size(), width = max<int>(1, int(sqrt(3) * n / sqrt(max(1, 2 * q))));
        vector<int> order(q);
        iota(order.begin(), order.end(), 0);
        sort(order.begin(), order.end(), [&](int a, int b) {
            const int ablock = left[a] / width, bblock = left[b] / width;
            if (ablock != bblock) return ablock < bblock;
            return (ablock & 1) ? (right[a] > right[b]) : (right[a] < right[b]);
        });
        int l = 0, r = 0;
        for (auto idx : order) {
            while (l > left[idx]) add(--l);
            while (r < right[idx]) add(r++);
            while (l < left[idx]) del(l++);
            while (r > right[idx]) del(--r);
            rem(idx);
        }
    }
};
int main() {
    int n, q;
    cin >> n >> q;
    string s;
    cin >> s;
    vector<int> sum(n + 1);
    for (int i = 0; i < n; ++i) sum[i + 1] = sum[i] + (s[i] == 'W' ? 1 : -1);
    Mo mo(n);
    for (int i = 0; i < q; ++i) {
        int l, r;
        cin >> l >> r;
        l--, r++;
        mo.add(l, r);
    }
    unordered_map<int, int> cnt;
    long long res = 0;
    vector<long long> ans(q);
    auto add = [&](int k) -> void {
        res += cnt[sum[k] - 1] + cnt[sum[k]] + cnt[sum[k] + 1];
        cnt[sum[k]]++;
    };
    auto del = [&](int k) -> void {
        cnt[sum[k]]--;
        res -= cnt[sum[k] - 1] + cnt[sum[k]] + cnt[sum[k] + 1];
    };
    auto rem = [&](int k) -> void {
        ans[k] = res;
    };
    mo.run(add, del, rem);
    for (int i = 0; i < q; ++i) cout << ans[i] << endl;
}