Description

Given a sequence $a_{1\sim n}$ and $q$ queries $(l, r)$,
find the minimum perimeter of a triangle whose three side lengths are $a_i, a_j, a_k$ satisfying $l \le i < j < k \le r$.
If no such triangle exists, output "yumi!".

Limitations

$1\le n\le 2.5\times 10^5$

$1\le q\le 5\times 10^5$

$1\le a_i\le 10^7$

$1\le l\le r\le n$

$4\text{s},512\text{MB}$

Solution

Partition the value range into blocks by powers of two: $[2^k,2^{k+1})$ is one block, total $O(\log V)$ blocks.

For a query, find the smallest $k$ such that the block contains $\ge 3$ numbers. Then we can freely choose inside this block, build a segment tree to maintain the smallest three values.

If there are $2\sim 3$ numbers before this block, extract all numbers before this block in ascending order and denote them as $t_i$. Obviously the longer two sides must be $t_i, t_{i+1}$; sweep with two pointers, take the smallest possible $j$ such that $(t_{i},t_{i+1},t_j)$ is valid. Note that the longest side can be inside this block.

If there is $1$ number before this block, denote it as $a_x$, obviously it is the smallest. Consider finding dominating pairs for each block. For the block containing $a_x$, the interval $a[l,r]$ can have at most $\le 2$ values in this block, otherwise it's not optimal. For each $a_x$ inside the block, let the leftmost/rightmost positions be $l,r$ that are valid. Let $b_i=\lfloor a_i/a_x\rfloor$; then if $(a_i,a_j,a_x)$ is valid we have $|b_i-b_j|\le 1$.

Enumerate numbers $a_j > a_x$ in $a[l,r]$; if $b_i=b_j$, maintain a monotonic stack for each occurring $b$ to store $a_i$; each time pop all $a_i\ge a_j$; $(a_i,a_j,a_x)$ is a dominating pair (the last stack top also counts). Otherwise it can be proved that $a_i$ must be taken as the first position to the left/right of $a_j$ satisfying $b_i=b_j-1$; record directly.

The number of dominating pairs is $O(n\log V)$. Use a sweep line + BIT to maintain and answer queries. Complexity $O(n\log n\log V+q\log V)$.