Solution *↵
↵
#If you still haven’t 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...](http://)↵
↵
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
↵
#If you still haven
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...](http://)↵
↵
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
