Buratsuta 3

Key Observation

For a segment of length $len$, there can be at most two values occurring strictly more than $\lfloor len/3\rfloor$ times.

If there were three different such values, their total occurrences would exceed $len$. So every answer line has size at most two.

That means we do not need to find all frequent-ish values. We only need a tiny list of candidates, then verify them exactly.

Counting A Candidate

Before answering queries, store all positions of every compressed value:

$$pos[x] = \{i : a_i = x\}.$$

Then the number of occurrences of $x$ in $[l,r]$ is:

$$\text{upper\_bound}(pos[x], r) - \text{lower\_bound}(pos[x], l).$$

So if someone hands us a candidate value, checking it is cheap: $O(\log n)$.

Now the actual problem is candidate generation.

Misra-Gries For One Segment

For threshold $1/3$, the generalized Boyer-Moore algorithm keeps two candidates and two counters.

When reading a value $x$:

• if $x$ is already candidate 1, increment counter 1;
• else if $x$ is already candidate 2, increment counter 2;
• else if some counter is zero, place $x$ there with count $1$;
• else $x$ is a third different value, so decrement both counters.

That last step is the whole trick. It cancels a triple of three different values. A value that appears more than one third of the segment cannot be fully killed by these cancellations. So every real answer must survive as one of the final two candidates.

Important: the counters are not the real frequencies. They are just residual votes after cancellation. Treating them as exact counts is how bugs sneak in wearing fake glasses.

Making It Work For Range Queries

Build a segment tree. Each node stores a Misra-Gries summary of its interval:

• up to two compressed values;
• their residual counters.

A leaf contains exactly one value with counter $1$.

To merge two children, start from the left summary and feed in the right summary's candidates with their residual weights. This is equivalent to saying: the right child has already canceled all irrelevant triples internally, and only its residual votes still matter for producing possible heavy hitters.

For threshold $1/3$, feeding a weighted candidate $(x,c)$ can be done directly:

• if $x$ is already stored, add $c$;
• else if an empty slot exists, put $(x,c)$ there;
• else we have three different candidates. Cancel as much as possible from all three. If $c$ is small, subtract it from both stored counters. If some stored counter is the smallest, remove that stored candidate and reduce the other two accordingly.

You can also insert $x$ one-by-one, but counters can be large, so the weighted version is cleaner.

For a query $[l,r]$, combine the $O(\log n)$ segment-tree nodes covering the range. The result gives at most two suspects. Then count those suspects exactly using the position lists.

Why The Segment Tree Summary Is Enough

Think of Misra-Gries as repeatedly deleting triples of distinct values. Deleting such triples cannot remove a value that is truly more than one third of the whole multiset from the candidate set forever, because every deleted triple removes at most one copy of that value while removing three total elements.

Each segment-tree node stores what remains after some valid triple deletions inside its interval. When two summaries are merged, we continue the same cancellation process on the remaining votes. So for the queried segment, the final two stored values are a superset of all values with frequency $> len/3$.

Then verification fixes everything:

• false candidates are removed;
• real candidates are kept;
• output order is handled by sorting original values.

No probability needed. No random sampling roulette. Deterministic AC, which is nicer because Codeforces RNG hacks are where dreams go to get mugged.

Complexity

Let $N$ and $Q$ be the total input sizes over all test cases.

• Coordinate compression: $O(N\log N)$
• Building the segment tree: $O(N)$ merges after compression
• Each query: $O(\log N)$ segment merges plus $O(\log N)$ verification for at most two candidates

Total complexity:

$$O((N+Q)\log N)$$

with $O(N)$ memory.