Blackslex and Plants

We need process range updates where the added pattern is not constant, not linear everywhere, and not even periodic by itself. So the obvious “difference array and vibe” plan dies immediately. The escape hatch is the lowbit.

For an offset $x$, write

$$\operatorname{lowbit}(x)=2^k.$$

That means $x$ is divisible by $2^k$ but not by $2^{k+1}$, equivalently

$$x\equiv 2^k \pmod {2^{k+1}}.$$

Then

$$f(x)=x\cdot 2^k.$$

So if we group offsets by their lowbit, the weird function becomes a linear function. That is the whole trick. Not magic, just binary being annoyingly helpful.

Splitting One Operation

Consider one watering operation $[l,r]$. Plant $i$ receives

$$f(i-l+1).$$

Let

$$x=i-l+1.$$

For a fixed $k$, the offsets with lowbit $2^k$ satisfy

$$x\equiv 2^k \pmod {2^{k+1}}.$$

Substitute $x=i-l+1$:

$$i-l+1\equiv 2^k \pmod {2^{k+1}},$$

so

$$i\equiv l-1+2^k \pmod {2^{k+1}}.$$

On exactly those positions, the contribution is

$$2^k(i-l+1)=2^k i+2^k(1-l).$$

That is of the form

$$A i+B,$$

where

$$A=2^k,\qquad B=2^k(1-l).$$

So every original update becomes about $\log n$ updates of this form:

add $A i+B$ to positions $i\in[l,r]$ having one specific residue modulo $2^{k+1}$.

Handling Residue-Class Range Updates

Fix a modulus

$$p=2^{k+1}.$$

For every residue $rem$, the positions with that residue are

$$rem,\ rem+p,\ rem+2p,\ldots$$

inside $[1,n]$.

Inside this list, any actual interval $[l,r]$ becomes one contiguous segment. Nice. So for each pair $(p,rem)$, we can keep difference arrays over that compressed list.

Because each update adds $A i+B$, we need two difference arrays:

• one for the coefficient of $i$;
• one for the constant term.

After all updates, prefix-sum those difference arrays. If position $i$ currently has coefficient sum $ca$ and constant sum $cb$, then it receives

$$ca\cdot i+cb.$$

Add that into the answer.

Finding The Segment In A Residue List

For a fixed modulus $p$ and residue $rem$, define the first positive position with that residue. Since positions are $1$-indexed, residue $0$ means the first position is $p$, otherwise it is $rem$.

Call this first position $first$.

The compressed index of a position $pos$ with the same residue is

$$\frac{pos-first}{p}.$$

For an update interval $[l,r]$, we need the first valid position at least $l$ and the last valid position at most $r$.

We can compute them with small helper functions:

• first_ge(l, p, rem) gives the first number $\ge l$ with that residue;
• last_le(r, p, rem) gives the last number $\le r$ with that residue.

If the first one is after the last one, that residue contributes nothing for this update.

Why The Size Is Fine

The moduli are powers of two:

$$2,4,8,16,\ldots$$

For modulus $p$, there are $p$ residue classes, but the total number of stored positions across all residues is just $n$. Across all powers, that is

$$O(n\log n).$$

Each operation creates one update per relevant $k$, also $O(\log n)$.

So the total complexity is

$$O((n+q)\log n)$$

per total input size, with memory also $O(n\log n)$. For $2\cdot 10^5$, that’s completely fine.

Overflow Check

A single contribution can be around

$$n\cdot \operatorname{lowbit}(n),$$

and there can be $2\cdot 10^5$ operations. This easily goes past 32-bit integers. Use long long. Letting int handle this would be a beautiful way to get wrecked by arithmetic, not by algorithms.