Overview

For each query \([L, R]\), we want to count the number of contiguous subintervals within it whose stones can be rearranged in an alternating black-white pattern.

The key insight is that if the difference between the number of white stones and black stones in an interval is at most \(1\), then they can be arranged in an alternating pattern.

Analysis

Let \(W\) be the number of white stones and \(B\) be the number of black stones in an interval.

The condition for being able to rearrange the stones in this interval so that no two adjacent stones share the same color is:

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

For example:

• If white and black counts are equal, like WBWB, it is possible.
• If one color has exactly \(1\) more than the other, like WBW, it is also possible.
• If the difference is \(2\) or more, like WWWB, no matter how you arrange them, same-colored stones will end up adjacent.

Therefore, for each interval, we only need to know the difference between the number of white and black stones.

Here, we convert each character of the string \(S\) into a numerical value as follows:

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

Then we define the prefix sum as:

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

with \(A_0 = 0\).

The difference between the number of white and black stones in the interval \([l, r]\) is:

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

Therefore, the condition for the interval \([l, r]\) to be a good interval is:

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

---

For a query \([L, R]\), we want to count the intervals \([l, r]\) satisfying:

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

In terms of prefix sum indices, this corresponds to pairs \((i, j)\) satisfying:

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

In other words, each query can be transformed into:

Among the pairs \((i, j)\) of elements within the range \([L-1, R]\) of the prefix sum array \(A\), count the number of pairs whose values differ by at most \(1\).

---

Naively checking all intervals for each query takes \(O(N^2Q)\) in the worst case, which is too slow given the constraints \(N, Q \leq 5 \times 10^4\).

To handle this efficiently, we use Mo’s algorithm, which can quickly update the number of pairs as the interval changes.

Algorithm

First, we build the prefix sum array \(A\).

W -> +1
B -> -1

We compute \(A_0, A_1, \dots, A_N\).

A query \([L, R]\) is transformed into the interval on the prefix sum array:

\[ [L-1, R] \]

The answer is the number of pairs of prefix sum values within this interval whose difference is \(0\) or \(1\).

---

In Mo’s algorithm, we answer each query by incrementally extending or shrinking the current interval to the left or right.

We maintain the frequency of prefix sum values in the current interval using freq.

When adding a new value \(x\), the existing values that can form a valid pair with \(x\) are:

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

Therefore, the increase in the answer from this addition is:

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

After that, we increment freq[x] by \(1\).

When removing a value, we do the reverse: first decrement freq[x] by \(1\), then subtract:

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

from the answer.

---

For example, suppose the current interval contains prefix sum values:

1, 2, 2, 4

If we add \(x = 3\), the existing values with a difference of at most \(1\) are:

2, 2, 4

So \(3\) new good pairs are added.

This is computed as:

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

Complexity

• Time complexity: \(O((N + Q)\sqrt{N} + Q \log Q)\)
• Space complexity: \(O(N + Q)\)

Implementation Notes

The prefix sum \(A_i\) can become negative.

Since negative values cannot be used directly as array indices, the code adds offset = N + 2 to shift all values to positive.

A[0] = offset;

After this, \(+1\) or \(-1\) is added to build the prefix sums.

Also, since a query \([L, R]\) becomes \([L-1, R]\) on the prefix sum array, we subtract \(1\) from the input \(L\) before storing it.

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

Since the answer counts the number of pairs, it can be as large as \(O(N^2)\).

Therefore, long long must be used instead of int.

Source Code

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

---

This editorial was generated by gpt-5.5-xhigh.