Overview

Given a sequence of black and white stones, this problem asks how many contiguous subintervals (good intervals) exist within a query-specified range such that the difference in the count of each color is at most 1.

Analysis

1. Rephrasing the “Good Interval” Condition

The condition “the stones can be freely rearranged so that all adjacent stones have different colors” becomes simple when we focus on the count of each color. Let \(N_W\) be the number of white stones and \(N_B\) be the number of black stones. The condition for alternating arrangement is equivalent to \(|N_W - N_B| \leq 1\). (Example: If there are 2 W’s and 1 B, we can arrange them as “WBW”, but with 3 W’s and 1 B, two W’s will inevitably be adjacent.)

2. Using Prefix Sums

For each stone, replace W with \(+1\) and B with \(-1\). The value \(N_W - N_B\) for the interval \([l, r]\) is the sum of these values. Define a prefix sum array \(P\) as \(P[i] = (\text{sum of values from the left up to the } i\text{-th position})\). Then the condition for interval \([l, r]\) to be a “good interval” can be written as: $\(|P[r] - P[l-1]| \leq 1\)\( In other words, it suffices that **the difference between \)P[r]\( and \)P[l-1]\( is at most \)1$**.

3. Handling Queries

For each query \((L_i, R_i)\), we need to count the number of pairs \((l, r)\) satisfying \(L_i \leq l \leq r \leq R_i\) that meet the above condition. In terms of prefix sum indices, this reduces to the problem of choosing two indices \(i, j\) (\(i < j\)) from the range \([L_i-1, R_i]\) and counting the number of combinations where \(|P[j] - P[i]| \leq 1\).

A brute-force approach would take \(O((R-L)^2)\) per query, resulting in \(O(QN^2)\) overall, which is too slow. To efficiently perform this “counting pairs within a range,” we use Mo’s algorithm.

Algorithm

Mo’s Algorithm

This is an offline algorithm that preprocesses queries by sorting them, then updates the answer by incrementally moving the interval endpoints.

1. Preparation: Compute the prefix sum \(P\). Add an offset of about \(N\) to all values to avoid negative indices.
2. Query Sorting: Sort the queries \([L_i-1, R_i]\) based on block decomposition so that the total movement of endpoints is minimized.
3. Maintaining State:
   • cnt[v]: The number of occurrences of prefix sum value v within the current interval.
   • current_ans: The total number of pairs satisfying the condition within the current interval.
4. Expansion/Contraction Operations:
   • When adding a value val to the interval, current_ans increases by the number of existing occurrences of val-1, val, and val+1 in the interval.
   • When removing a value val from the interval, current_ans decreases by the remaining number of occurrences of val-1, val, and val+1 in the interval.

Complexity

• Time Complexity: \(O((N + Q)\sqrt{N})\)
  • Building the prefix sum takes \(O(N)\).
  • The total movement of endpoints in Mo’s algorithm is \(O((N + Q)\sqrt{N})\).
  • Each operation (addition/removal) runs in \(O(1)\).
• Space Complexity: \(O(N + Q)\)
  • Required for the prefix sum array, the occurrence count array cnt, and storing the queries.

Implementation Notes

• Index Offset: Since the prefix sum \(P[i]\) can be as small as \(-N\), you need to shift values upward, e.g., P[i] += N + 1, to use them as array indices.

• Fast I/O: Since \(N, Q\) can be as large as \(5 \times 10^4\), in C++ it is standard practice to speed up I/O with ios::sync_with_stdio(false); cin.tie(nullptr);.

• Mo’s Algorithm Optimization: When sorting queries, alternating the direction of right endpoint movement for each block (zigzag traversal) can improve performance by a constant factor.

  Source Code

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>

using namespace std;

/**
 * Problem: Good Intervals in a range [L, R]
 * A range is "good" if its stones can be rearranged such that no two adjacent stones have the same color.
 * This condition is equivalent to |count(W) - count(B)| <= 1.
 * Let P[i] be the prefix sum where 'W' is +1 and 'B' is -1.
 * The condition for range [l, r] is |P[r] - P[l-1]| <= 1.
 * For each query (Li, Ri), we need to count pairs (i, j) such that Li-1 <= i < j <= Ri and |P[j] - P[i]| <= 1.
 * This can be solved efficiently using Mo's algorithm.
 */

struct Query {
    int l, r, id, block;
    // Standard Mo's algorithm sorting with alternating r direction optimization
    bool operator<(const Query& other) const {
        if (block != other.block) return block < other.block;
        return (block % 2 == 0) ? (r < other.r) : (r > other.r);
    }
};

int main() {
    // Fast I/O for competitive programming
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, Q;
    if (!(cin >> N >> Q)) return 0;
    string S;
    cin >> S;

    // Calculate prefix sums where 'W' contributes +1 and 'B' contributes -1
    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);
    }

    // Shift prefix sum values to be non-negative for use as array indices
    // Original range is [-N, N], shifted range is [1, 2N+1]
    for (int i = 0; i <= N; ++i) {
        P[i] += N + 1;
    }

    // Determine block size for Mo's algorithm
    int block_size = max(1, (int)(N / sqrt(Q + 1)));
    vector<Query> queries(Q);
    for (int i = 0; i < Q; ++i) {
        int L, R;
        cin >> L >> R;
        queries[i].l = L - 1; // Range of indices in P is [Li-1, Ri]
        queries[i].r = R;
        queries[i].id = i;
        queries[i].block = queries[i].l / block_size;
    }

    // Sort queries based on Mo's algorithm order
    sort(queries.begin(), queries.end());

    // cnt[v] stores the frequency of value v in the current range of P
    // current_ans stores the number of pairs (i, j) in the range satisfying |P[j] - P[i]| <= 1
    vector<int> cnt(2 * N + 5, 0);
    vector<long long> results(Q);
    long long current_ans = 0;
    int cur_l = 0, cur_r = -1;

    // Add an element to the current range
    auto add = [&](int idx) {
        int val = P[idx];
        // Count existing elements P[k] such that |val - P[k]| <= 1
        current_ans += (long long)cnt[val - 1] + cnt[val] + cnt[val + 1];
        cnt[val]++;
    };

    // Remove an element from the current range
    auto remove = [&](int idx) {
        int val = P[idx];
        cnt[val]--;
        // Subtract pairs involving the removed element that satisfy the condition
        current_ans -= (long long)cnt[val - 1] + cnt[val] + cnt[val + 1];
    };

    // Process each query using Mo's algorithm pointers
    for (int i = 0; i < Q; ++i) {
        int L = queries[i].l;
        int R = queries[i].r;
        while (cur_l > L) add(--cur_l);
        while (cur_r < R) add(++cur_r);
        while (cur_l < L) remove(cur_l++);
        while (cur_r > R) remove(cur_r--);
        results[queries[i].id] = current_ans;
    }

    // Output all results in the order of the original queries
    for (int i = 0; i < Q; ++i) {
        cout << results[i] << "\n";
    }

    return 0;
}

---

This editorial was generated by gemini-3-flash-thinking.