Queries on Values (Editorial)

Main Idea

Consider two consecutive occurrences of the same value $x$ at positions $i$ and $j$, that is,

Initially, every element with value $x$ can be considered to require a separate operation. However, sometimes two consecutive occurrences of $x$ can be zeroed within the same sequence of operations, which means that the second occurrence does not increase the answer.

This is possible if and only if for every position $k$ such that i<k<j, the following two conditions hold:

1. a_k>x;

2. a_k\le R.

The first condition means that there is no element between the two equal values $x$ that becomes zero earlier than or at the same time as them and prevents us from merging these two occurrences.

The second condition means that all elements between them are allowed to be changed in the current query. Since x\in[L,R] and all intermediate values are strictly greater than $x$, the lower bound $L$ is satisfied automatically. Therefore, it is enough to check only the upper bound $R$.

Let cnt_x be the number of elements in the array equal to $x$. Initially, set

The value res_x represents the number of operations contributed to the answer by elements with value $x$.

Whenever two consecutive occurrences of $x$ can be merged, we decrease res_x by $1$.

First Condition

We process the array from left to right and maintain pos_x — the last position where the value $x$ occurred.

Suppose the current position is $j$, a_j=x, and the previous occurrence of $x$ is at position

We need to check that

The minimum on a segment can be found using a segment tree.

It is important to query exactly the segment

without including positions $i$ and $j$ themselves, since both contain the value $x$.

If i+1>j-1, meaning that the two equal elements are adjacent, this condition is satisfied automatically.

If there is no previous occurrence of $x$, then there is nothing to merge the current element with.

Second Condition

For every pair of consecutive occurrences of $x$ that passed the first check, compute

Such a pair can be merged in a query if and only if

Therefore, for every valid pair we create an event

This event means that for every query with R\ge mx, we may decrease

by one.

Sort all events by $mx$, and sort all queries by their right border $R$.

We process queries in increasing order of $R$. Before answering the current query, activate all events for which

When activating an event $(mx,x)$, perform

Answering a Query

For a query $[L,R]$, we are interested only in the initial values that belong to this interval.

Therefore, the answer is

To maintain the array $res$, we can use a Fenwick tree or a segment tree.

Initially, we store cnt_x at position $x$. When an event is activated, we perform a point update by $-1$, and for each query we compute the sum on the segment $[L,R]$.

Thus, all queries can be processed offline.

The overall time complexity is O((n+q)\log n).

The memory complexity is O(n+q).