概要

\(M=2^N\) とおくと、二分割で現れるグループは「長さが \(2,4,8,\dots,M\) の、区切り位置がそろった区間」です。
長さ \(K\) の区間を左から右へずらしながら、変更される場所だけをセグメント木で更新して、均衡グループ数の最大値を求めます。

考察

均衡グループの条件

あるグループの長さを \(len\)、その中の 1 の個数を \(cnt\) とします。

赤は 0、白は 1 なので、赤と白の人数が等しい条件は

\(cnt = len - cnt\)

つまり

\(2 \times cnt = len\)

です。

また、\(1\) 人のグループは均衡グループにならないため、長さ \(2\) 以上のグループだけを考えれば十分です。

二分割で現れるグループは、0-indexed で見ると、

• 長さ \(2,4,8,\dots,M\)
• 左端がその長さの倍数

である区間です。

---

素朴にやると間に合わない

操作する区間の左端は最大で \(M-K+1\) 通りあります。

各操作後の文字列について、すべてのグループを数え直すと、グループ数は \(O(M)\) 個あるため、

\(O(M^2)\)

になってしまいます。
\(M \leq 10^6\) なのでこれは間に合いません。

---

操作後の文字列の形

操作する区間を \([l,r)\) とします。ここで \(r=l+K\) です。

この区間内の 1 の個数を \(c\) とすると、0 の個数は \(K-c\) です。
操作後、区間内は

• 先頭 \(K-c\) 個が 0
• 残り \(c\) 個が 1

になります。

つまり、境界位置を

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

とすると、

• \([l,t)\) は 0
• \([t,r)\) は 1

になります。

例えば \(K=5\) で区間内に 1 が \(2\) 個なら、操作後は 00011 になります。

---

区間を1つ右にずらしたときの変化

現在の操作区間を \([l,r)\)、次を \([l+1,r+1)\) とします。

現在の 1 の個数を \(c\)、次の 1 の個数を \(c'\) とすると、

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

です。

現在の境界を \(t\)、次の境界を \(t'\) とすると、

\(t = r-c\)

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

なので、

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

です。

\(S_l,S_r\) はそれぞれ 0 または 1 なので、

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

となります。

つまり、操作区間を1つ右にずらしても、境界位置は高々 \(2\) しか動きません。

したがって、操作後の文字列で変わる可能性がある場所は、

• 左端から外れる位置 \(l\)
• 新しく右端に入る位置 \(r\)
• 境界が動いた部分 \([t,t')\)

だけです。

これは高々定数個の位置です。

---

1点変更で均衡グループ数を更新する

ある位置の値が 0 から 1、または 1 から 0 に変わったとします。

そのとき、影響を受けるグループは、その位置を含むグループだけです。
二分割で現れるグループでは、各長さごとにその位置を含む区間は1つだけなので、影響を受ける区間数は

\(O(\log M)\)

個です。

そこで、完全二分木に対応するセグメント木を使います。

各ノードに、その区間内の 1 の個数を持たせます。
さらに、現在の均衡グループ数 balanced を管理します。

1点更新するときは、その位置の祖先ノードだけを見て、

1. 更新前に均衡なら balanced を \(1\) 減らす
2. 1 の個数を更新する
3. 更新後に均衡なら balanced を \(1\) 増やす

という処理を行います。

これで1点更新あたり \(O(\log M)\) で均衡グループ数を保てます。

アルゴリズム

\(M=2^N\) とします。

1. 元の文字列について、累積和を作る。
2. 操作しない場合の均衡グループ数を数え、答えの初期値にする。
   • 長さ \(2,4,8,\dots,M\) の区間をすべて見る。
   • 区間内の 1 の個数が長さの半分なら均衡グループ。
3. 左端 \(l=0\) の操作後の文字列を作る。
   • 最初の \(K\) 文字を、0 が先、1 が後になるようにする。
4. その文字列でセグメント木を構築し、現在の均衡グループ数を求める。
5. 操作区間の左端 \(l\) を \(0\) から \(M-K\) まで動かす。
   • 現在の balanced で答えを更新する。
   • 次の左端へ動かすとき、変化する可能性がある定数個の位置だけを1点更新する。
6. 最大値を出力する。

計算量

\(M=2^N\) とします。

• 時間計算量: \(O(M \log M)\)
• 空間計算量: \(O(M)\)

操作区間をずらす回数は \(O(M)\) 回で、各回に高々定数個の1点更新を行います。
1点更新はセグメント木上で \(O(\log M)\) です。

実装のポイント

• 1 の個数を管理すれば、均衡条件は \(2 \times cnt = len\) で判定できます。

• 操作を行わない場合も選べるため、元の文字列での均衡グループ数を答え候補に入れておきます。

• 区間を右にずらすとき、境界位置の移動量は \(0,1,2\) のいずれかなので、更新する場所は高々定数個です。

• 同じ位置を複数回更新対象にしてしまうことがありますが、値が変わらなければ何もしないようにすれば問題ありません。

  ソースコード

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

---

この解説は gpt-5.5-xhigh によって生成されました。