CSES - Bit Inversions

We can use a Segment Tree over the given array of bits. Assume, for now, that we are querying for the longest continuous subsegment of 1s. In a node of the segment tree corresponding to range $[l, r]$, we will store three pieces of information:

• The longest prefix of 1s in the range $[l, r]$ (denote this as $P$)
• The longest suffix of 1s in the range $[l, r]$ (denote this as $S$)
• The longest subarray of 1s in the range $[l, r]$ (denote this as $A$)
• The length of the subarray (equivalent to $r - l + 1$) (denote this as $L$)

To merge left child $a$ and right child $b$ to make node $c$

• If $a.P = a.L$, then $c.P = a.L + b.P$; otherwise, $c.P = a.P$
• If $b.S = b.L$, then $c.S = b.L + a.S$; otherwise, $c.S = b.S$
• $c.A = \max(a.A, b.A, a.S + b.P)$
• $c.L = a.L + b.L$

A bit flip operation corresponds to a point update on the segment tree and a longest homogeneous subarray query corresponds to the $A$ value of the root node. We can thus handle all operations efficiently. Note that using two segment trees that are inverses of each other (one for the 0s and one for the 1s) makes the implementation easier.

Time Complexity: $\mathcal{O}((N + Q)\log N)$

Copy
#include <bits/stdc++.h>
using namespace std;

struct node {
	int P, S, A, L;
} val0{0, 0, 0, 1}, val1{1, 1, 1, 1};

node operator+(const node &a, const node &b) {
	return {a.P == a.L ? a.L + b.P : a.P, b.S == b.L ? b.L + a.S : b.S,
	        max(max(a.A, b.A), a.S + b.P), a.L + b.L};