CSES - Bit Inversions

Author: Dustin Miao

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][l, r], we will store three pieces of information:

  • The longest prefix of 1s in the range [l,r][l, r] (denote this as PP)
  • The longest suffix of 1s in the range [l,r][l, r] (denote this as SS)
  • The longest subarray of 1s in the range [l,r][l, r] (denote this as AA)
  • The length of the subarray (equivalent to rl+1r - l + 1) (denote this as LL)

To merge left child aa and right child bb to make node cc

  • If a.P=a.La.P = a.L, then c.P=a.L+b.Pc.P = a.L + b.P; otherwise, c.P=a.Pc.P = a.P
  • If b.S=b.Lb.S = b.L, then c.S=b.L+a.Sc.S = b.L + a.S; otherwise, c.S=b.Sc.S = b.S
  • c.A=max(a.A,b.A,a.S+b.P)c.A = \max(a.A, b.A, a.S + b.P)
  • c.L=a.L+b.Lc.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 AA 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: O((N+Q)logN)\mathcal{O}((N + Q)\log N)


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

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!