Odd Queries on Odd Array

The condition is the whole problem. If you ignore it, you get baited into Mo's algorithm, but the queries are online, so nope. If you try plain prefix beauties, that also dies because beauty is a parity set, not a normal additive sum.

So we need to use the structure forced by cute arrays.

The Tree Hidden In The Array

Cute means there is no subsequence $x,y,x,y$ with $x\ne y$.

That says two values cannot have crossing occurrence ranges. If value $x$ starts, then value $y$ starts inside it, then $x$ appears again, then $y$ appears again, we have exactly the forbidden pattern. So the ranges are nested or disjoint. That screams stack.

Add a fake vertex $0$ with value $0$. Let $first[x]$ and $last[x]$ be the first and last positions of value $x$. Build a rooted tree like this:

• Start with stack $[0]$.
• For each position $i=1\ldots n$, make vertex $i$ a child of the stack top.
• If $i=first[a_i]$, push $i$.
• If $i=last[a_i]$, pop.

Why is popping valid? Suppose we are at the last occurrence of $x$, but some value $y$ opened after the first $x$ is still on the stack. Then we have

$first[x] < first[y] < last[x] < last[y],$

which gives the forbidden subsequence $x,y,x,y$. So cute arrays make the stack behave. Nice for once.

The DFS preorder of this tree is exactly $0,1,2,\ldots,n$, because every new vertex is appended as the next DFS visit. So a subarray is a contiguous preorder interval in this tree.

Also, non-first occurrences are leaves. Only first occurrences get pushed, so only they can later receive children.

What We Need To Answer

For a range $[l,r]$, find $u=\operatorname{lca}(l,r)$ in this tree. The preorder interval $[l,r]$ splits into at most three useful parts:

1. A suffix of the child subtree of $u$ that contains $l$.
2. A middle chunk consisting of $u$ and whole child subtrees of $u$.
3. A prefix of the child subtree of $u$ that contains $r$.

The middle is the annoying part because multiple occurrences of $a_u$ can appear as direct children of $u$, and their parity must be counted together. Treating those singleton children independently is the classic off-by-one-but-actually-wrong trap.

Precomputations

First compute normal prefix and suffix beauties by toggling parity:

• $pref[i]$ is the beauty of $a[1\ldots i]$.
• $suff[i]$ is the beauty of $a[i+1\ldots n]$.

So $suff[l-1]$ is the beauty of $a[l\ldots n]$.

Next compute, for every first-occurrence vertex $v$:

• $lastIn[v]$: the largest index in the DFS subtree of $v$.
• $sub[v]$: the beauty of the whole subtree interval $[v,lastIn[v]]$.

To compute $sub[v]$, process vertices from $n$ down to $0$. If $v$ is a first occurrence, look at its children. A child that is another first occurrence contributes its whole $sub[child]$. A child with the same value as $v$ is just another occurrence of $a_v$, so it toggles the parity bit for $a_v$.

So conceptually:

$sub[v] = \sum sub[child] + [\text{the value } a_v \text{ appears oddly inside this component}]\cdot a_v.$

The fake root has value $0$, so its parity bit is harmless.

Prefix Tables Over Children

For each first-occurrence vertex $v$, let its children be

$c_0,c_1,\ldots,c_{d-1}.$

Build a table over boundaries around these children. Each state stores two things:

• sum: total beauty from completed child subtrees.
• bit: parity of occurrences of $a_v$ seen so far, counting $v$ itself and same-valued direct child leaves.

We encode the pair as 2 * sum + bit.

Boundary meanings:

• boundary $0$: before $v$, state $(0,0)$.
• boundary $1$: after taking $v$, state $(0,1)$.
• boundary $j+2$: after also taking children $c_0\ldots c_j$.

If we need the middle chunk between two boundaries $L$ and $R$, decode both states. The answer is

$sum_R - sum_L + (bit_L \oplus bit_R)\cdot a_v.$

That is the whole reason we store the parity bit separately. Without it, same-valued direct children would quietly break the answer.

Answering A Query

If $l=r$, answer $a_l$.

Otherwise compute $u=\operatorname{lca}(l,r)$.

For the left side:

• If $l=u$, the middle starts before $u$, so pl = 0.
• Else if $l$ is a direct non-first child of $u$, leave it for the middle, because it is another occurrence of $a_u$. Set pl = pos(l)+1.
• Otherwise let $c$ be the child of $u$ that is an ancestor of $l$. Add the suffix piece $[l,lastIn[c]]`. This equals

$suff[l-1] - suff[lastIn[c]],$

because values inside that full child subtree do not occur outside it. Then set pl = pos(c)+2, meaning the middle starts after that child.

For the right side:

• If $r=u$, the middle ends after $u, so pr = 0`.
• Else if $r$ is a direct non-first child of $u$, include it in the middle: pr = pos(r)+1.
• Otherwise let $c$ be the child of $u$ that is an ancestor of $r$. Add the prefix piece $[c,r]`, which is

$pref[r] - pref[c-1].$

Then set pr = pos(c), meaning the middle ends before that child.

Finally add the middle contribution from acc[u][pl] to acc[u][pr+1].

Finding the child of $u$ that contains a node is done by binary lifting: lift the node upward while its ancestor is still strictly below $u$.

Correctness Sketch

The stack tree is valid because any value opened inside another value must close before the outer value closes. Otherwise we directly get $x,y,x,y$, which is forbidden.

The subtree of a first-occurrence child is independent from the outside: every value that starts inside it finishes inside it, again because crossing would form $x,y,x,y$. Therefore whole child subtrees can be added using sub, and partial prefixes/suffixes can be extracted using global pref/suff differences.

The only values that can appear across several direct children of a node $u$ are copies of $a_u$ itself. Those direct non-first children are leaves, and the accumulator table handles their parity together with $u$. That is why the middle formula is exact.

The query decomposition covers every index in $[l,r]$ exactly once: left partial child suffix, middle whole-child run around the LCA, and right partial child prefix. Each part contributes exactly the values with odd parity inside that part, and the only cross-part parity interaction is $a_u$, handled by the middle bit. So the computed value is exactly the beauty of $a[l\ldots r]$.

Preprocessing costs $O(n\log n)$ for binary lifting and $O(n)$ for all beauty tables. Each query costs $O(\log n)$. With total $n,q\le 5\cdot 10^5$, this is comfortably AC.