# Binary Alchemy↵
↵
Time limit: 2.0 seconds↵
Memory limit: 256 MB↵
↵
You are given a dynamic binary string `S` of length `N`.↵
↵
The string changes over time through point flips.↵
↵
For any binary string `T`, define `val(T)` as the integer represented by the last `min(60, |T|)` characters of `T`, where the rightmost character is the least significant bit.↵
↵
Also define `popcount(x)` as the number of set bits in the binary representation of `x`.↵
↵
---↵
↵
## Queries↵
↵
You must process `Q` queries of two types.↵
↵
### Type 1 — Flip↵
↵
`1 i`↵
↵
Flip the `i`-th character of `S`.↵
↵
That is:↵
↵
* `0` becomes `1`↵
* `1` becomes `0`↵
↵
---↵
↵
### Type 2 — Balanced Partition Optimization↵
↵
`2 l r k`↵
↵
Let:↵
↵
`L = r - l + 1`↵
↵
It is guaranteed that:↵
↵
`1 ≤ k ≤ L`↵
↵
Split `S[l..r]` into exactly `k` non-empty contiguous parts:↵
↵
`S[l..r] = P₁ + P₂ + ... + Pₖ`↵
↵
The partition must be balanced, meaning each part has length either:↵
↵
`floor(L / k)`↵
↵
or↵
↵
`ceil(L / k)`↵
↵
For a partition, define:↵
↵
`X = val(P₁) ⊕ val(P₂) ⊕ ... ⊕ val(Pₖ)`↵
↵
Your task is to maximize:↵
↵
`popcount(X)`↵
↵
over all valid balanced partitions.↵
↵
---↵
↵
## Input Format↵
↵
* First line: integers `N` and `Q`↵
* Second line: binary string `S`↵
* Next `Q` lines:↵
↵
`1 i`↵
`2 l r k`↵
↵
---↵
↵
## Output Format↵
↵
For each query of type `2`, output the maximum possible value of `popcount(X)`.↵
↵
---↵
↵
## Example↵
↵
### Input↵
↵
`5 5↵
10101↵
2 1 5 2↵
1 3↵
2 1 5 2↵
2 2 4 2↵
2 1 3 1`↵
↵
### Output↵
↵
`3↵
2↵
0↵
1`↵
↵
---↵
↵
## Explanation↵
↵
Initial string:↵
↵
`10101`↵
↵
### Query: `2 1 5 2`↵
↵
Balanced partitions have lengths `2` and `3`.↵
↵
Possible splits:↵
↵
`10 | 101`↵
↵
`2 ⊕ 5 = 7`↵
`popcount(7) = 3`↵
↵
and↵
↵
`101 | 01`↵
↵
`5 ⊕ 1 = 4`↵
`popcount(4) = 1`↵
↵
The maximum is `3`.↵
↵
---↵
↵
### Query: `1 3`↵
↵
Flip the 3rd character:↵
↵
`10101 -> 10001`↵
↵
---↵
↵
### Query: `2 1 5 2`↵
↵
The best answer is `2`.↵
↵
---↵
↵
### Query: `2 2 4 2`↵
↵
The substring is:↵
↵
`000`↵
↵
Any balanced split gives XOR `0`, so the answer is `0`.↵
↵
---↵
↵
### Query: `2 1 3 1`↵
↵
Only one part exists:↵
↵
`100`↵
↵
`val(100) = 4`↵
`popcount(4) = 1`↵
↵
---↵
↵
## Constraints↵
↵
`1 ≤ N, Q ≤ 2 · 10^5`↵
`S[i] ∈ {0,1}`↵
`1 ≤ i ≤ N`↵
`1 ≤ l ≤ r ≤ N`↵
`1 ≤ k ≤ 10`↵
`r - l + 1 ≤ 60 · k`↵
↵
---↵
↵
## Notes↵
↵
* `val(T)` depends only on the last at most `60` bits.↵
* Since `r - l + 1 ≤ 60 · k`, every part has length at most `60`.↵
↵
Time limit: 2.0 seconds↵
Memory limit: 256 MB↵
↵
You are given a dynamic binary string `S` of length `N`.↵
↵
The string changes over time through point flips.↵
↵
For any binary string `T`, define `val(T)` as the integer represented by the last `min(60, |T|)` characters of `T`, where the rightmost character is the least significant bit.↵
↵
Also define `popcount(x)` as the number of set bits in the binary representation of `x`.↵
↵
---↵
↵
## Queries↵
↵
You must process `Q` queries of two types.↵
↵
### Type 1 — Flip↵
↵
`1 i`↵
↵
Flip the `i`-th character of `S`.↵
↵
That is:↵
↵
* `0` becomes `1`↵
* `1` becomes `0`↵
↵
---↵
↵
### Type 2 — Balanced Partition Optimization↵
↵
`2 l r k`↵
↵
Let:↵
↵
`L = r - l + 1`↵
↵
It is guaranteed that:↵
↵
`1 ≤ k ≤ L`↵
↵
Split `S[l..r]` into exactly `k` non-empty contiguous parts:↵
↵
`S[l..r] = P₁ + P₂ + ... + Pₖ`↵
↵
The partition must be balanced, meaning each part has length either:↵
↵
`floor(L / k)`↵
↵
or↵
↵
`ceil(L / k)`↵
↵
For a partition, define:↵
↵
`X = val(P₁) ⊕ val(P₂) ⊕ ... ⊕ val(Pₖ)`↵
↵
Your task is to maximize:↵
↵
`popcount(X)`↵
↵
over all valid balanced partitions.↵
↵
---↵
↵
## Input Format↵
↵
* First line: integers `N` and `Q`↵
* Second line: binary string `S`↵
* Next `Q` lines:↵
↵
`1 i`↵
`2 l r k`↵
↵
---↵
↵
## Output Format↵
↵
For each query of type `2`, output the maximum possible value of `popcount(X)`.↵
↵
---↵
↵
## Example↵
↵
### Input↵
↵
`5 5↵
10101↵
2 1 5 2↵
1 3↵
2 1 5 2↵
2 2 4 2↵
2 1 3 1`↵
↵
### Output↵
↵
`3↵
2↵
0↵
1`↵
↵
---↵
↵
## Explanation↵
↵
Initial string:↵
↵
`10101`↵
↵
### Query: `2 1 5 2`↵
↵
Balanced partitions have lengths `2` and `3`.↵
↵
Possible splits:↵
↵
`10 | 101`↵
↵
`2 ⊕ 5 = 7`↵
`popcount(7) = 3`↵
↵
and↵
↵
`101 | 01`↵
↵
`5 ⊕ 1 = 4`↵
`popcount(4) = 1`↵
↵
The maximum is `3`.↵
↵
---↵
↵
### Query: `1 3`↵
↵
Flip the 3rd character:↵
↵
`10101 -> 10001`↵
↵
---↵
↵
### Query: `2 1 5 2`↵
↵
The best answer is `2`.↵
↵
---↵
↵
### Query: `2 2 4 2`↵
↵
The substring is:↵
↵
`000`↵
↵
Any balanced split gives XOR `0`, so the answer is `0`.↵
↵
---↵
↵
### Query: `2 1 3 1`↵
↵
Only one part exists:↵
↵
`100`↵
↵
`val(100) = 4`↵
`popcount(4) = 1`↵
↵
---↵
↵
## Constraints↵
↵
`1 ≤ N, Q ≤ 2 · 10^5`↵
`S[i] ∈ {0,1}`↵
`1 ≤ i ≤ N`↵
`1 ≤ l ≤ r ≤ N`↵
`1 ≤ k ≤ 10`↵
`r - l + 1 ≤ 60 · k`↵
↵
---↵
↵
## Notes↵
↵
* `val(T)` depends only on the last at most `60` bits.↵
* Since `r - l + 1 ≤ 60 · k`, every part has length at most `60`.↵
