Overview

Define a “good interval” as a subarray of black and white stones that can be rearranged to alternate colors. For each query, count the number of good intervals within a specified range. We solve this efficiently by combining a reformulation using prefix sums with Mo’s algorithm.

Analysis

Organizing the Conditions for a Good Interval

Let \(w\) be the number of white stones and \(b\) be the number of black stones in the interval \([l, r]\). To arrange them alternately, the more frequent color must exceed the less frequent color by at most 1. That is:

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

Reformulation Using Prefix Sums

Define a prefix sum array \(p\) where white is \(+1\) and black is \(-1\):

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

Then the difference between white and black counts in the interval \([l, r]\) is \(p[r] - p[l-1]\), so the condition for a good interval becomes:

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

Reduction to a Pair Counting Problem

For a query \((L, R)\), counting good intervals with \(L \leq l \leq r \leq R\) can be rephrased in terms of prefix sum indices \(a = l-1\), \(b = r\):

In the prefix sum array \(p\), over the index range from \(L-1\) to \(R\), count the number of pairs \((a, b)\) with \(a < b\) and \(|p[a] - p[b]| \leq 1\).

Issue with the Naive Approach

Checking all pairs for each query takes \(O((R - L)^2)\), resulting in \(O(N^2 Q)\) in the worst case, which is too slow.

Algorithm

Mo’s Algorithm

We use Mo’s algorithm, an offline algorithm that efficiently processes range queries.

1. Preprocessing: Transform each query \((L_i, R_i)\) into a query \((L_i - 1, R_i)\) on the prefix sum array.
2. Query Sorting: Group queries by the left endpoint into blocks of size \(\sqrt{N}\), and within the same block, sort by the right endpoint.
3. Interval Extension/Contraction: Incrementally extend or contract the current interval \([\text{cl}, \text{cr}]\) by one element at a time to answer each query.

Add / Remove Operations

When adding an element with value \(v = p[\text{idx}]\), the number of new “good pairs” formed with elements already in the interval is:

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

• \(\text{freq}[v]\): pairs with difference \(0\)
• \(\text{freq}[v-1]\), \(\text{freq}[v+1]\): pairs with difference \(\pm 1\)

After adding, increment \(\text{freq}[v]\). Removal is performed in the reverse order.

Concrete Example

For \(S = \text{BWW}\), we have \(p = [0, -1, 0, 1]\).

For the query on interval \([1, 3]\), we look at the \(p\) values \(\{0, -1, 0, 1\}\) at indices \(\{0, 1, 2, 3\}\) and count pairs with \(|p[a] - p[b]| \leq 1\):

Pair \((a,b)\)	\(p[a], p[b]\)	Absolute Difference	Good?
\((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\)	✓

The number of good intervals is 5.

Complexity

• Time complexity: \(O((N + Q) \sqrt{N})\)
  • The number of interval extensions/contractions in Mo’s algorithm is \(O((N + Q)\sqrt{N})\), and each operation is \(O(1)\)
• Space complexity: \(O(N + Q)\)
  • For the prefix sum array, frequency array, and storage of queries and answers

Implementation Notes

• Shifting the prefix sum value range: Since \(p[i]\) can range over \([-N, N]\), we use p[idx] + N as the frequency array index to shift values to non-negative.

• Order of add and remove: In Mo’s algorithm, it is important to perform extension operations (add) before contraction operations (remove). This prevents the interval from becoming empty.

• Mo’s algorithm sorting optimization: Sort by ascending right endpoint for even-numbered blocks and by descending right endpoint for odd-numbered blocks (zigzag method) to reduce the total movement of the right endpoint.

  Source Code

#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;
}

---

This editorial was generated by claude4.6opus-thinking.