Triple Attack

The condition says no three chosen attacks may fit inside a time window of length $z$. Since the timestamps are sorted, that has a much cleaner form.

Take the chosen positions in increasing order:

$a_1<a_2<\dots<a_k.$

The subset is safe iff

$x_{a_{i+2}}-x_{a_i}>z$

for every valid $i$.

Why? Any bad triple has some earliest and latest chosen element, and if those two are not within two consecutive selected positions, then the three consecutive selected positions inside that range are bad too. So checking consecutive triples is enough. Nice. The quadratic triple hell disappears.

The Greedy Shape

For each index $i$, define

$nxt[i]=\min\{j : j>i \text{ and } x_j>x_i+z\}.$

If no such $j$ exists, let $nxt[i]=n+1$.

Suppose we already selected some position $a_i$. Then the position two places later, $a_{i+2}$, must satisfy

$x_{a_{i+2}}-x_{a_i}>z.$

So the earliest possible choice is exactly $nxt[a_i]$.

For a fixed query interval $[l,r]$, if it has at least two elements, we should start with $l$ and $l+1$. This is one of those greedies that looks suspicious but is actually just common sense with paperwork: replacing the first selected element by an earlier one cannot make future choices worse, because $nxt$ is monotone with index. Same for the second selected element. Earlier choices leave at least as much room as later choices.

Then the sequence is forced greedily:

$a_1=l,\quad a_2=l+1,$

and

$a_{i+2}=nxt[a_i].$

So the selected positions split into two chains:

$l, nxt[l], nxt[nxt[l]], \dots$

and

$l+1, nxt[l+1], nxt[nxt[l+1]], \dots$

The answer is the number of chain elements from both chains that are still at most $r$.

Tiny example of the structure:

• first chain gives selected positions $a_1,a_3,a_5,\dots$;
• second chain gives selected positions $a_2,a_4,a_6,\dots$.

The safety condition only connects positions two apart, so this split is not a hack. It is the whole damn trick.

Why This Is Optimal

Let an optimal selected sequence inside $[l,r]$ be

$b_1<b_2<\dots<b_k.$

We can greedily compare it with our sequence $a$.

Clearly $a_1=l\le b_1$ and, if $k\ge 2$, $a_2=l+1\le b_2$.

Now assume $a_i\le b_i$. Since $x$ is sorted,

$x_{a_i}\le x_{b_i}.$

The next valid position two steps later for $a_i$ is no later than the next valid position two steps later for $b_i$:

$nxt[a_i]\le nxt[b_i].$

Also, because $b$ is safe, $b_{i+2}$ itself is a valid choice after $b_i$, so

$nxt[b_i]\le b_{i+2}.$

Therefore

$a_{i+2}=nxt[a_i]\le b_{i+2}.$

By induction, every greedy-selected position is no later than the matching position in any optimal solution. So if some solution can select $k$ elements within $r$, the greedy sequence can also select $k$ elements within $r$. Greedy is optimal. No vibes-based proof, no handwaving.

Answering Queries Fast

Now every query asks for chain lengths:

$ans(l,r)=cnt(l,r)+cnt(l+1,r),$

where $cnt(s,r)$ is how many times we can start at $s$ and repeatedly apply $nxt$ while staying $\le r$.

If $s>r$, then $cnt(s,r)=0$.

To compute $cnt(s,r)$ quickly, use binary lifting on the function $nxt$:

$up[0][i]=nxt[i],$

$up[p][i]=up[p-1][up[p-1][i]].$

Then to count from $s$:

1. Start with current index $cur=s$ and answer $1$.
2. Try large powers of two downward.
3. If jumping $2^p$ times lands at an index $\le r$, take that jump and add $2^p$.

This counts all reachable chain nodes within the query interval.

We include sentinel index $n+1$ where all jumps stay at $n+1$, so bounds stay clean.

Complexity

For each test case:

• Building $nxt$: $O(n\log n)$ using upper_bound, or $O(n)$ with two pointers. The code below uses two pointers.
• Building binary lifting: $O(n\log n)$.
• Each query: $O(\log n)$.

Across all test cases, $\sum n,\sum q\le 250000$, so this easily fits. The problem is rated 2500, but once you see the two-chain thing, it folds like a cheap lawn chair.