Overview

Let \(M=2^N\). The groups that appear in binary partitioning are “intervals of length \(2,4,8,\dots,M\) with aligned boundary positions.”
We slide an interval of length \(K\) from left to right, updating only the changed positions using a segment tree, to find the maximum number of balanced groups.

Discussion

Condition for Balanced Groups

Let \(len\) be the length of a group and \(cnt\) be the number of 1s in it.

Since red is 0 and white is 1, the condition for equal numbers of red and white people is:

\(cnt = len - cnt\)

That is:

\(2 \times cnt = len\)

Also, a group of \(1\) person cannot be a balanced group, so it suffices to consider only groups of length \(2\) or more.

The groups that appear in binary partitioning, viewed in 0-indexed terms, are intervals where:

• The length is \(2,4,8,\dots,M\)
• The left endpoint is a multiple of that length

---

The Naive Approach Is Too Slow

The left endpoint of the operation interval has at most \(M-K+1\) possible values.

If we recount all groups for the string after each operation, since there are \(O(M)\) groups, the complexity becomes:

\(O(M^2)\)

Since \(M \leq 10^6\), this is too slow.

---

Shape of the String After the Operation

Let the operation interval be \([l,r)\), where \(r=l+K\).

If the number of 1s in this interval is \(c\), then the number of 0s is \(K-c\).
After the operation, within the interval:

• The first \(K-c\) characters are 0
• The remaining \(c\) characters are 1

In other words, defining the boundary position as:

\(t = l + (K-c) = r-c\)

we have:

• \([l,t)\) is all 0
• \([t,r)\) is all 1

For example, if \(K=5\) and there are \(2\) ones in the interval, the result after the operation is 00011.

---

Changes When Shifting the Interval One Position to the Right

Let the current operation interval be \([l,r)\) and the next be \([l+1,r+1)\).

If the current number of 1s is \(c\) and the next is \(c'\), then:

\(c' = c - S_l + S_r\)

If the current boundary is \(t\) and the next is \(t'\), then:

\(t = r-c\)

\(t' = (r+1)-c'\)

So:

\(t' - t = 1 + S_l - S_r\)

Since \(S_l\) and \(S_r\) are each 0 or 1:

\(t' - t \in \{0,1,2\}\)

This means that even when shifting the operation interval one position to the right, the boundary position moves by at most \(2\).

Therefore, the positions that may change in the string after the operation are only:

• Position \(l\) that leaves the left end
• Position \(r\) that newly enters the right end
• The part \([t,t')\) where the boundary moved

This is at most a constant number of positions.

---

Updating the Balanced Group Count with Point Updates

Suppose the value at some position changes from 0 to 1, or from 1 to 0.

Then, only the groups containing that position are affected.
In the groups from binary partitioning, for each length, there is exactly one interval containing that position, so the number of affected intervals is:

\(O(\log M)\)

Therefore, we use a segment tree corresponding to a complete binary tree.

Each node stores the number of 1s within its interval.
Additionally, we maintain the current balanced group count balanced.

When performing a point update, we only look at the ancestor nodes of that position and:

1. If it was balanced before the update, decrease balanced by \(1\)
2. Update the count of 1s
3. If it is balanced after the update, increase balanced by \(1\)

This allows us to maintain the balanced group count in \(O(\log M)\) per point update.

Algorithm

Let \(M=2^N\).

1. Build a prefix sum array for the original string.
2. Count the number of balanced groups without any operation, and set it as the initial answer.
   • Check all intervals of length \(2,4,8,\dots,M\).
   • If the number of 1s in an interval equals half its length, it is a balanced group.
3. Construct the string after the operation with left endpoint \(l=0\).
   • Rearrange the first \(K\) characters so that 0s come first and 1s come after.
4. Build the segment tree for this string and compute the current balanced group count.
5. Move the left endpoint \(l\) of the operation interval from \(0\) to \(M-K\).
   • Update the answer with the current balanced value.
   • When moving to the next left endpoint, perform point updates only on the constant number of positions that may change.
6. Output the maximum value.

Complexity

Let \(M=2^N\).

• Time complexity: \(O(M \log M)\)
• Space complexity: \(O(M)\)

The operation interval is shifted \(O(M)\) times, and each time at most a constant number of point updates are performed.
Each point update takes \(O(\log M)\) on the segment tree.

Implementation Notes

• By maintaining the count of 1s, the balanced condition can be checked as \(2 \times cnt = len\).

• Since we can also choose not to perform any operation, the balanced group count for the original string should be included as an answer candidate.

• When shifting the interval to the right, the boundary position moves by \(0\), \(1\), or \(2\), so the number of positions to update is at most constant.

• The same position may be targeted for update multiple times, but this is not a problem as long as we do nothing when the value doesn’t actually change.

  Source Code

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

struct BalancedSegTree {
    int n, logn;
    vector<int> sum;
    vector<unsigned char> val;
    long long balanced = 0;

    BalancedSegTree(int n_, int logn_, const vector<unsigned char>& init)
        : n(n_), logn(logn_), sum(2 * n_, 0), val(init) {
        for (int i = 0; i < n; i++) sum[n + i] = val[i];
        for (int i = n - 1; i >= 1; i--) sum[i] = sum[i << 1] + sum[i << 1 | 1];

        for (int d = 0; d < logn; d++) {
            int len = n >> d;
            int l = 1 << d, r = 1 << (d + 1);
            for (int i = l; i < r; i++) {
                if (sum[i] * 2 == len) balanced++;
            }
        }
    }

    void set_point(int pos, int x) {
        int old = val[pos];
        if (old == x) return;

        int delta = x - old;
        val[pos] = (unsigned char)x;

        int idx = n + pos;
        sum[idx] = x;
        idx >>= 1;

        int len = 2;
        while (idx > 0) {
            if (sum[idx] * 2 == len) balanced--;
            sum[idx] += delta;
            if (sum[idx] * 2 == len) balanced++;

            idx >>= 1;
            len <<= 1;
        }
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, K;
    string S;
    cin >> N >> K >> S;

    int M = 1 << N;

    vector<unsigned char> orig(M);
    vector<int> pref(M + 1, 0);
    for (int i = 0; i < M; i++) {
        orig[i] = (unsigned char)(S[i] - '0');
        pref[i + 1] = pref[i] + orig[i];
    }

    long long no_operation = 0;
    for (int len = 2; len <= M; len <<= 1) {
        for (int l = 0; l < M; l += len) {
            int ones = pref[l + len] - pref[l];
            if (ones * 2 == len) no_operation++;
        }
    }

    int ones_win = pref[K];
    int t0 = K - ones_win;

    vector<unsigned char> cur = orig;
    for (int i = 0; i < t0; i++) cur[i] = 0;
    for (int i = t0; i < K; i++) cur[i] = 1;

    BalancedSegTree seg(M, N, cur);

    long long ans = no_operation;
    int max_l = M - K;

    for (int l = 0; l <= max_l; l++) {
        ans = max(ans, seg.balanced);

        if (l == max_l) break;

        int r = l + K;
        int t = l + K - ones_win;

        int next_ones = ones_win - (int)orig[l] + (int)orig[r];
        int nl = l + 1;
        int nr = r + 1;
        int nt = nl + K - next_ones;

        auto desired = [&](int p) -> int {
            if (p < nl || p >= nr) return orig[p];
            return (p >= nt) ? 1 : 0;
        };

        auto apply = [&](int p) {
            if (0 <= p && p < M) seg.set_point(p, desired(p));
        };

        apply(l);
        apply(r);
        for (int p = t; p < nt; p++) apply(p);

        ones_win = next_ones;
    }

    cout << ans << '\n';
    return 0;
}

---

This editorial was generated by gpt-5.5-xhigh.