自动搬运

查看原文

来自洛谷，原作者为

	wwwwwza RP++

搬运于2025-08-24 23:12:39，当前版本为作者最后更新于2025-04-30 21:36:14，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

先将值域按 $[2^k,2^{k+1})$ 分块。

显然，在一个块内，怎么取都是满足三角形三遍关系的。所以对于每一个询问，找到最小的块满足在询问区间中含有至少 $3$ 个数。线段树维护即可，因为询问比较多，所以要用前缀和找出满足条件的块。

• 如果有两个或三个元素 $<2^k$。

假设这三个元素是 $(a,b,c)$，那么 $b$ 和 $c$ 一定是相邻的，若 $b<p<c$，那么选 $(a,b,p)$ 一定更优。

因为对于每个 $i<k$ 在值域 $[2^i,2^{i+1})$ 中最多含有两个数，不然 $k$ 还能更小。

那么在值域 $[1,2^k)$ 中的数的个数是 $\log V$ 级别的。

因为较长边和最长边长度相邻，所以直接枚举较长边在哪。当 $i<j$ 时 $(a,lst_i,lst_{i+1})$ 比 $(b,lst_j,lst_{j+1})$ 更优，那么 $a>b$，换句话说就是 $lst_{i+1}-lst_{i}>lst_{j+1}-lst_j$，直接单调栈维护就可以了。

最长边的数值可以 $\ge 2^k$，不要忘记处理。

• 如果有一个元素 $<2^k$。

那么这个元素一定是最小值，令这个元素为 $a_x$。

正着算不太好做，考虑在询问区间是什么时能取到最短边为 $a_x$ 的情况。

显然，询问区间不能包含三个即以上个与 $a_x$ 所在值域块相同的值（包含 $a_x$），这个区间可以预处理出来。显然，所有区间的长度和是 $n\log V$ 级别的。

将所有 $>a_x$ 的数拿出来处理。

设 $b_i=\left \lfloor \frac{a_i}{a_x} \right \rfloor$，当 $(a_i,a_j,a_x)$ 满足条件时，$\left | b_i-b_j \right | \le 1$ 也一定满足。

当 $\left | b_i-b_j \right | =0$ 时。

所有 $(a_i,a_j,a_x)$ 都满足条件，但是有些区间被支配了，其实是没有用的。

考虑用一个单调栈，每加入一个数 $a_i$，就将 $\ge a_i$ 的数弹出，这些数与 $a_i$ 不会被支配。除此之外， $a_i$ 与栈顶的元素也会形成一个支配对。（至于为什么可以画下图）。

注意开 $V$ 个单调栈会 MLE，考虑只开 $K$ 个单调栈，对于每个块单独做，这里的复杂度是 $O(n\log V \frac{V}{K})$，不过无伤大雅。

支配对数量是线性的。

当 $\left | b_i-b_j \right | =1$ 时。

显然 $j$ 一定在 $i$ 左边或右边第一个满足 $b_j=b_i-1$ 的位置，这个画下图就知道了。

这个的支配对数量也是线性的。

总的支配对数量是 $n\log V$ 级别的，树状数组和扫描线维护。

总时间复杂度为 $O(n\log V\log n+q\log V)$。

有没有人能告诉我不放代码的传统是从什么时候开始的。

想要的可以私信问我。