Solution *

If you still havent solved the problem, you can access it through this link :

https://mirror.codeforces.com/blog/entry/154038

'

include <bits/stdc++.h>

using namespace std;

using ull = unsigned long long;

static const ull MASK60 = (1ULL << 60) — 1;

static ull win[605]; static ull valSmall[605]; static ull valLarge[605]; static ull mask[61];Your text to link here...

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

for (int len = 1; len <= 60; ++len) {
    mask[len] = (1ULL << len) - 1;
}

int N, Q;
string S;
cin >> N >> Q >> S;
S = " " + S; // 1-indexed

while (Q--) {
    int type;
    cin >> type;

    if (type == 1) {
        int i;
        cin >> i;
        S[i] = (S[i] == '0' ? '1' : '0');
    } else {
        int l, r, k;
        cin >> l >> r >> k;

        int L = r - l + 1;

        int small = L / k;
        int large = small + 1;
        int cntLarge = L % k;
        int cntSmall = k - cntLarge;

        ull cur = 0;
        for (int i = 0; i < L; ++i) {
            cur = ((cur << 1) | (S[l + i] - '0')) & MASK60;
            win[i] = cur;
        }

        for (int pos = 0; pos + small <= L; ++pos) {
            valSmall[pos] = win[pos + small - 1] & mask[small];
        }

        if (cntLarge > 0) {
            for (int pos = 0; pos + large <= L; ++pos) {
                valLarge[pos] = win[pos + large - 1] & mask[large];
            }
        }

        int ans = 0;


        auto dfs = [&](auto&& self, int idx, int pos,
                       int remSmall, int remLarge, ull xr) -> void {
            if (idx == k) {
                ans = max(ans, __builtin_popcountll(xr));
                return;
            }

            if (remSmall > 0) {
                self(self, idx + 1, pos + small,
                     remSmall - 1, remLarge,
                     xr ^ valSmall[pos]);
            }

            if (remLarge > 0) {
                self(self, idx + 1, pos + large,
                     remSmall, remLarge - 1,
                     xr ^ valLarge[pos]);
            }
        };

        dfs(dfs, 0, 0, cntSmall, cntLarge, 0ULL);

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

return 0;

} '

. Solution Explanation

This solution is based on brute force over all valid balanced partitions for each type-2 query.

At first glance, the presence of point updates and range queries strongly suggests using a segment tree or dynamic programming. However, such approaches are unnecessary — and in fact overkill — due to a crucial constraint:

• k ≤ 10
• r — l + 1 ≤ 60 · k

This means the total length of the processed substring is at most 600, and more importantly, every part in any valid partition has length at most 60.

As a result, instead of maintaining complex data structures, we can process each query independently and directly enumerate all valid balanced partitions.

Key Observation

Let:

• L = r — l + 1
• small = floor(L / k)
• large = small + 1

In any balanced partition:

• exactly cntLarge = L % k parts have length large
• exactly cntSmall = k — cntLarge parts have length small

So the only choice is the order of these lengths.

The number of valid orders is:

C(k, cntLarge)

Since k ≤ 10, this is at most 252.

So for each type-2 query, we can simply try all valid orders.

Fast Computation of val(T)

For a binary string T, val(T) is the integer formed by the last min(60, |T|) bits.

We scan S[l..r] once and maintain a rolling value:

cur = ((cur << 1) | bit) & MASK60

This keeps only the last 60 bits.

Let win[i] be the value of the suffix ending at position i inside the current query range.

Then for a segment starting at pos with length len:

val = win[pos + len — 1] & mask[len]

Since every part length is at most 60, this gives the exact value of that part.

Enumerating All Valid Partitions

We use DFS to enumerate every valid sequence of part lengths.

At each step:

• if we still need a small part, choose one
• if we still need a large part, choose one

We maintain:

• idx: how many parts have already been chosen
• pos: current position in the substring
• remSmall: how many small parts remain
• remLarge: how many large parts remain
• xr: XOR of all chosen parts so far

When idx == k, we have a complete balanced partition, so we compute:

popcount(xr)

and update the answer.

This is exactly what the code does.

Correctness

Every valid balanced partition corresponds to exactly one sequence of small and large part lengths.

The DFS generates all such sequences.

For each sequence, the code computes the exact XOR of all parts and takes the maximum popcount.

Therefore, the algorithm always returns the correct answer.

Complexity

For one type-2 query:

• Building rolling suffix values: O(L)
• Precomputing part values: O(L)
• DFS enumeration: at most C(k, cntLarge) ≤ 252

So the total complexity is:

O(L + C(k, cntLarge))

Since L ≤ 60k ≤ 600 and k ≤ 10, this is easily fast enough.

Type-1 queries are O(1).

Conclusion

Although the problem may initially appear to require advanced data structures, the tight constraints reduce it to a manageable brute force over all valid balanced partitions. The key insight is that only the order of small and large parts matters, and there are very few such orders