Masha and the Garland

The whole problem collapses to one fact: if a queried segment contains $c$ equal adjacent pairs, then its exact minimum number of operations is

$$\left\lceil \frac{c}{2}\right\rceil.$$

Once we prove that, static prefix sums handle every query.

Bad boundaries

Call the boundary between bulbs $i$ and $i+1$ bad if

$$s_i=s_{i+1}.$$

A binary segment is beautiful if and only if none of its internal boundaries are bad. Indeed, once every adjacent pair differs, the segment must be one of the two alternating patterns, depending only on its first bit.

For a query $[l,r]$, let

$$c=\#\{i\mid l\le i<r,\ s_i=s_{i+1}\}.$$

So our job is simply to turn all $c$ bad boundaries into good ones.

What one flip can change

Suppose we flip a subsegment $[x,y]$. Consider any adjacent pair:

• If both bulbs are flipped, equality is preserved: 00 becomes 11, 11 becomes 00, and unequal pairs stay unequal.
• If neither bulb is flipped, obviously nothing changes.
• If exactly one bulb is flipped, equality reverses: a bad boundary becomes good, or a good boundary becomes bad.

Only the boundaries immediately outside the flipped subsegment, between $x-1,x$ and between $y,y+1$, have exactly one endpoint flipped. Therefore one operation changes at most two boundary states inside the queried segment.

Operations extending outside $[l,r]$ offer no secret loophole: intersecting such an operation with $[l,r]$ flips exactly the same queried bulbs. We may therefore assume every useful operation lies inside the query.

Since one operation can fix at most two bad boundaries, any solution needs at least

$$\left\lceil \frac{c}{2}\right\rceil$$

operations.

The lower bound is attainable

List the bad boundaries in increasing order:

$$p_1<p_2<\dots<p_c,$$

where boundary $p_j$ lies between bulbs $p_j$ and $p_j+1$.

Take two consecutive bad boundaries $p_{2j-1}$ and $p_{2j}$ and flip

$$[p_{2j-1}+1,\ p_{2j}].$$

At boundary $p_{2j-1}$, only the right bulb is flipped. At boundary $p_{2j}$, only the left bulb is flipped. Thus both bad boundaries become good. Every boundary strictly between them has both bulbs flipped, so its state is unchanged. No other internal boundary is touched.

This fixes each pair of bad boundaries with one operation. If $c$ is odd, one bad boundary $p_c$ remains; flipping

$$[p_c+1,r]$$

changes that boundary and no other internal boundary of the query.

Hence we can always succeed in

$$\left\lfloor\frac c2\right\rfloor+(c\bmod 2) =\left\lceil\frac c2\right\rceil$$

operations. Combined with the lower bound, this is the exact optimum. The interval-flip drama was really just endpoint bookkeeping.

Answering all queries

Define

$$a_i=[s_i=s_{i+1}]\qquad(1\le i<n)$$

and prefix sums

$$P[0]=0,\qquad P[i]=\sum_{j=1}^{i}a_j.$$

The bad boundaries internal to $[l,r]$ have indices $l,l+1,\dots,r-1$, so

$$c=P[r-1]-P[l-1].$$

The answer is therefore YES exactly when

$$\frac{c+1}{2}\le k,$$

where the division is integer division. This also handles $l=r$: then $c=0$, and a one-bulb segment is already beautiful.

Correctness proof

For every query $[l,r]$:

1. A segment is beautiful exactly when all its internal bad boundaries have been removed.
2. Any interval flip changes at most two internal boundary states, so removing $c$ bad boundaries requires at least $\lceil c/2\rceil$ operations.
3. Pairing bad boundaries and flipping between each pair removes two per operation without changing any others; an odd leftover is removed by flipping a suffix of the query.
4. Therefore the minimum required number of operations is exactly $\lceil c/2\rceil$, which the algorithm compares with $k$.

Thus every printed answer is correct.

Complexity

For each test case, preprocessing takes $O(n)$ time. Every query takes $O(1)$ time, for total time $O(n+q)$ and memory $O(n)$.