长夜伴浪破晓梦，梦晓破浪伴夜长。

P10882 [JRKSJ R9] ZYPRESSEN

• 给出序列 $(a_1,\dots,a_n)$。$q$ 次询问 $l,r$，求 $l\le i<j<k\le r$ 且存在以 $a_i,a_j,a_k$ 为三边长度的三角形的三元组 $(i,j,k)$ 的 $a_i+a_j+a_k$ 最小值。
• $n\le 2.5\times 10^5$，$q\le 5\times 10^5$，$a_i\le 10^7$。

• 若存在 $2$ 个 $<2^m$ 的元素
  注意到找到的是最小的 $m$ 使得 $(a_l,\dots,a_r)$ 在 $B_m$ 中有 $\ge3$ 个元素，因此对于编号为 $[1,m)$ 的块，$(a_l,\dots,a_r)$ 中的元素在其中的出现次数 $\le 2$，即前 $m-1$ 个块总共只有 $\mathcal{O}(\log |V|)$ 个元素。先把她们全部找出来。可以考虑维护每个位置前 / 后（包含这个位置）第一个块内元素（前驱 / 后继），然后找 $l$ 的后继和 $r$ 的前驱即可。注意仅有 $1$ 个元素时不要重复找。可以对于每个询问维护一个容器，枚举到每个块时，若 $(a_l,\dots,a_r)$ 中的元素在其中的出现次数 $\le 2$，就找出 $\mathcal{O}(1)$ 个元素插入对应询问的容器里。还需要有序。但是从小到大枚举值域块已经保证块间的顺序了，只要在插入 $\mathcal{O}(1)$ 个元素时判断大小关系即可。
  不妨认为 $a_i\le a_j\le a_k$，则 $a_i\le a_j<2^m$。若 $(i,j,k)$ 能产生贡献，则区间中一定不存在 $(a_j,a_k)$ 内的元素，不然最长边更换成她一定更优。换言之 $k$ 一定是区间中除了 $a_i,a_j$ 以外最小的 $\ge a_j$ 的元素。那么 $a_k$ 一定在找出来的 $\mathcal{O}(\log |V|)$ 个元素中或者在 $(a_l,\dots,a_r)$ 内 $B_k$ 中最小的元素。若 $(a_l,\dots,a_r)$ 内没有 $B_k$ 中的元素则不用考虑，因为 $k$ 以后的块中的元素是无法和 $a_i,a_j$ 产生贡献的。
  记找出来的元素集合非降排序后为 $(s_1,\dots,s_t)$，枚举 $s_u$ 作为 $a_j$，则 $a_k=s_{u+1}$。此时需要找到最小的 $v$ 使得 $s_v>s_{u+1}-s_u$。注意到 $u$ 递增时若 $s_{u+1}-s_u$ 也递增，则 $a_j,a_k$ 两条边长度变大，$a_i$ 这条边的限制也变大，一定不优。因此只要考虑 $s_{u+1}-s_u$ 为前缀最小值的情况，此时她单调递减，因此 $s_v$ 也单调不升，用双指针维护即可。
  每个询问仅在找到对应的 $m$ 后才会触发双指针统计，因此时间复杂度为 $\mathcal{O}(q\log |V|)$。
• 若仅有 $1$ 个 $<2^m$ 的元素。
  此时 $a_i$ 是最短边。考虑枚举这个元素 $a_i$ 在第 $w$ 块。可以在枚举每一块的时候处理其中的所有元素。记 $i$ 前第 $x$ 个与 $a_i$ 同块的元素位置为 $\text{pre}_x$，$i$ 后第 $x$ 个同块元素位置为 $\text{nxt}_x$，则仅需要考虑 $(\text{pre}_2,\text{nxt}_2)$ 内的 $j,k$，否则若一个询问需要用到这之外的 $j,k$ 构成的 $(i,j,k)$ 的询问，则至少包含 $\text{pre}_2,\text{pre}_1,i$ 或 $i,\text{nxt}_1,\text{nxt}_2$ 这三个 $B_w$ 内的元素。而 $a_i$ 已经是最短边了，所以 $a_j,a_k\ge 2^w$。则此时 $(i,j,k)$ 这个三元组一定不如 $B_w$ 块内前三小值优。而满足在询问区间中有至少三个元素的块 $b$ 一定 $\le w$。因此 $(i,j,k)$ 就没有贡献了。
  而对于 $B_w$ 内的元素而言 $|(\text{pre}_2,\text{nxt}_2)|$ 的总和是 $\mathcal{O}(n)$ 的，考虑每对相邻的同块元素的间距只会在 $\mathcal{O}(1)$ 个区间中产生贡献。而间距的总和是 $\mathcal{O}(n)$ 的。那么对于所有块，区间长度总和就是 $\mathcal{O}(n\log |V|)$。
  这时就可以直接枚举区间内大于 $a_i$ 的元素了。钦定 $a_k$ 为 $a_j,a_k$ 中较大元素，若 $a_j=a_k$，则钦定 $a_k$ 为靠右的元素。令 $e_x=\left\lfloor\dfrac{a_x}{a_i}\right\rfloor$，则 $(i,j,k)$ 合法的 必要条件 是 $e_k-e_j\le 1$。
  若 $e_k=e_j$，则任意 $(i,j,k)$ 都可行。直接把所有点对找出来不可接受，考虑找支配对。对于两个 本质不同 的点对，称 $(i,j_1,k_1)$ 支配了 $(i,j_2,k_2)$ 当且仅当 $\min\{j_2,k_2\}\le \min\{j_1,k_1\}\le \max\{j_1,k_1\}\le \max\{j_2,k_2\}$ 且 $a_i+a_{j_1}+a_{k_1}\le a_{i}+a_{j_2}+a_{k_2}$。容易发现若一个点对被支配，则她对任何一个询问都没有贡献，因为若她在询问的区间内，则支配她的点对也在询问的区间内，且和更小。我们发现有贡献的点对一定满足在大于 $a_i$ 且 $e_k=e_j$ 的位置中，$a_j$ 是 $k$ 左边第一个 $\le a_k$ 的元素，或 $k$ 右边第一个 $<a_k$ 的元素。给出前者的证明：
  假使存在 $j<p<k$ 使得 $a_i<a_j,a_p\le a_k$，若 $a_p<a_j$，则 $(i,p,k)$ 支配了 $(i,j,k)$；否则 $(i,j,p)$ 支配了 $(i,j,k)$。后者的证明类似。
  那么就可以枚举 $k$，然后对于每种 $e_k$ 维护单调栈就可以得到 $j$ 的位置了。
  若 $e_k=e_j+1$，则有贡献的点对一定满足 $j$ 一定是 $k$ 左 / 右第一个 $e_j=e_k-1$ 的位置。给出在左边情况的证明：假使存在 $j<p<k$ 使得 $e_j=e_p=e_k-1$，则 $(i,j,p)$ 支配了 $(i,j,k)$，右边的情况类似。
  此时，我们发现对于每个 $a_i$ 的区间内的位置 $k$，都找出了关于她的 $\mathcal{O}(1)$ 个可能有贡献的点对，因此总共有 $\mathcal{O}(n\log |V|)$ 个点对。对于一次询问只需要考虑这些点对即可，相当于查询 $\min\{i,j,k\}\ge l,\max\{i,j,k\}\le r$ 的点对中 $a_i+a_j+a_k$ 的最小值，直接扫描线配合树状数组维护即可。

AC Link / Code