Overview

Each group that appears through recursive splitting is an interval whose length is a power of \(2\) and whose boundaries are aligned.
We perform at most one operation that rearranges the portion of length \(K\) so that “red is on the left, white is on the right,” and we find the maximum number of groups with equal numbers of red and white people.

Analysis

Groups correspond to intervals in a segment tree

Let the number of students be \(M=2^N\).

The groups formed by recursively splitting in half are the following intervals:

• The entire interval
• The left half and right half
• Further halves of those
• \(\dots\)

This corresponds exactly to each node of a complete binary tree over an array of length \(M\), i.e., a segment tree.

If the length of an interval is \(L\), the condition for that interval to be a balanced group is:

• The number of white hats is \(L/2\)
• The number of red hats is also \(L/2\)

If we treat character 1 as a white hat, then the interval is a balanced group if the count of 1s in it equals \(L/2\).

Note that intervals of length \(1\) cannot be balanced groups, so we do not count leaves.

---

Naively trying all candidates is too slow

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

For each left endpoint, if we:

1. Rearrange the interval
2. Check whether each group is balanced

then each candidate takes \(O(M)\) time, and the total is \(O(M^2)\).

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

---

The results of adjacent operation intervals differ in only a few places

The key observation is that when we shift the left endpoint from \(l\) to \(l+1\), the resulting sequence changes in at most \(4\) positions.

From here on, indices are \(0\)-based, and intervals are half-open \([l,l+K)\).

Let \(z\) be the number of red hats, i.e., 0s, contained in the operation interval \([l,l+K)\).
After the operation, the interval becomes:

• \([l,l+z)\) is 0
• \([l+z,l+K)\) is 1

Define the boundary as:

\[ p = l+z \]

Next, we shift the left endpoint to \(l+1\). Let \(r=l+K\), so the new interval is \([l+1,r+1)\).

Let \(z'\) be the new count of 0s:

\[ z' = z - [S_l=0] + [S_r=0] \]

Treating 0 and 1 as numerical values, this can be written as:

\[ z' = z + S_l - S_r \]

The new boundary is:

\[ q = l+1+z' \]

Then:

\[ q-p = 1 + S_l - S_r \]

so \(q-p\) is one of \(0,1,2\).

This means the number of positions whose contents change due to the boundary shift is at most \(2\).

Furthermore:

• The left endpoint \(l\) leaves the operation interval
• The right endpoint \(r\) newly enters the operation interval

so each of these causes at most \(1\) change.

Therefore, each time we shift the left endpoint by \(1\), the number of changed positions is at most:

\[ 1+2+1=4 \]

---

A single-position change can be handled with a segment tree update

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

The only groups affected are those whose intervals contain that position.
In the segment tree, only the ancestor nodes from that position’s leaf up to the root are affected.

The number of ancestor nodes is \(O(\log M)\).

For each node:

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

This allows us to maintain the current balanced group count through updates.

Algorithm

Let \(M=2^N\).

1. Compute the case with no operation

First, compute the balanced group count for the original string \(S\).
This serves as an answer candidate.

In the segment tree, each node stores the count of 1s in its interval.

For a node with interval length \(L\), the group is balanced if its count of 1s equals \(L/2\).

---

2. Construct the result of the operation with left endpoint \(0\)

Next, construct the result of rearranging the interval \([0,K)\).

Let \(z\) be the count of 0s in this interval, then:

• Set \([0,z)\) to 0
• Set \([z,K)\) to 1

Build the segment tree for this state and compute the balanced group count.

---

3. Update while sliding the left endpoint

Let the current left endpoint be \(l\) and the right endpoint be \(r=l+K\).

Let the current count of 0s be \(z\), and the boundary be:

\[ p=l+z \]

For the next left endpoint \(l+1\), compute:

\[ z' = z + S_l - S_r \]

\[ q = l+1+z' \]

The positions that may change are as follows:

Left endpoint \(l\)

Position \(l\) leaves the operation interval and reverts to its original value \(S_l\).

Currently, position \(l\) is 0 if \(z>0\).
Therefore, a change of

\[ 0 \to 1 \]

occurs only when \(S_l=1\) and \(z>0\).

Common part \([l+1,r)\)

Currently the boundary is \(p\), and next it is \(q\).

Since \(q-p\) is at most \(2\), the positions that change are contained in:

\[ [p,q) \cap [l+1,r) \]

which is at most \(2\) positions.

These change as:

\[ 1 \to 0 \]

Right endpoint \(r\)

Position \(r\) newly enters the operation interval.

If the new interval contains at least one 1, i.e., \(z'<K\), then the last position \(r\) in the interval becomes 1.

Therefore, a change of

\[ 0 \to 1 \]

occurs only when \(S_r=0\) and \(z'<K\).

---

4. Update the segment tree for each changed position

For a position that:

• Changes from 0 to 1: apply +1
• Changes from 1 to 0: apply -1

and update the count of 1s for all nodes containing that position.

For each node, check whether it is balanced before and after the update, and update the current balanced group count.

For each left endpoint, reflect the current balanced group count in the answer candidates.

The final maximum is the answer.

Complexity

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

where \(M=2^N\).

The initial segment tree construction and balanced group count computation take \(O(M)\).
After that, each shift of the left endpoint updates at most \(4\) positions, and each update takes \(O(\log M)\), so the total is \(O(M \log M)\).

Implementation Notes

• Each node of the segment tree stores the count of 1s in its interval.

• A node of length \(2\) is a balanced group if its count of 1s is \(1\); a node of length \(4\) is balanced if its count is \(2\); in general, it is balanced if the count equals half the interval length.

• Leaves, i.e., intervals of length \(1\), cannot be balanced groups and are not counted.

• Since not performing any operation is also allowed, the balanced group count of the original string must always be included as an answer candidate.

• When sliding the left endpoint, instead of rebuilding the entire interval, we only update the at most \(4\) positions that change.

  Source Code

import sys

def main():
    input = sys.stdin.buffer.readline
    N, K = map(int, input().split())
    trans = bytes.maketrans(b'01', b'\x00\x01')
    s = input().strip().translate(trans)

    M = 1 << N
    base = M
    tree = [0] * (base * 2)

    def rebuild_count():
        t = tree
        for i in range(base - 1, 0, -1):
            t[i] = t[i << 1] + t[(i << 1) | 1]

        bal = 0
        start = base >> 1
        end = base
        half = 1
        while start:
            cnt = 0
            for i in range(start, end):
                if t[i] == half:
                    cnt += 1
            bal += cnt
            end = start
            start >>= 1
            half <<= 1
        return bal

    tree[base:base + M] = s
    original_bal = rebuild_count()

    z = K - sum(s[:K])

    tree[base:base + M] = s
    if z:
        tree[base:base + z] = bytes(z)
    ones = K - z
    if ones:
        tree[base + z:base + K] = b'\x01' * ones

    bal = rebuild_count()
    ans = original_bal if original_bal > bal else bal

    def add_delta(pos, delta, cur_bal):
        t = tree
        idx = (pos + base) >> 1
        half = 1
        while idx:
            x = t[idx]
            if x == half:
                cur_bal -= 1
            x += delta
            t[idx] = x
            if x == half:
                cur_bal += 1
            idx >>= 1
            half <<= 1
        return cur_bal

    p = z
    limit = M - K

    for l in range(limit):
        r = l + K
        sl = s[l]
        sr = s[r]

        z2 = z + sl - sr
        q = l + 1 + z2

        if sl and z:
            bal = add_delta(l, 1, bal)

        a = p
        lp1 = l + 1
        if a < lp1:
            a = lp1
        b = q
        if b > r:
            b = r

        if a < b:
            bal = add_delta(a, -1, bal)
            a += 1
            if a < b:
                bal = add_delta(a, -1, bal)

        if sr == 0 and z2 < K:
            bal = add_delta(r, 1, bal)

        z = z2
        p = q

        if bal > ans:
            ans = bal

    print(ans)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.5-high.