自动搬运

查看原文

来自洛谷，原作者为

	critnos 咔菲好喝。

搬运于2025-08-24 23:02:09，当前版本为作者最后更新于2024-04-05 19:11:54，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

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

然后从小到大扫描每个块，如果这个块中有 $\ge 3$ 个数在区间中就停下来，记这个块是 $t$。

首先可知，存在一个方案是这个块内前三小值的和。这就说明，其他的方案至少包含一个 $<t$ 的块中的数。

接下来考虑所有 $<t$ 的块中的数，只有 $O(\log v)$ 个。

如果答案包含这其中的 $\ge 2$ 个数，这个是容易计算的。可以发现，答案的最大、次大值在排序数组中相邻。那么只需要取出 $<t$ 的块中的数和块 $t$ 中的最小值计算这些数的答案。

对于已经排序的数组，可以线性计算答案。小到大枚举合法的 $i,a_i-a_{i-1}<a_{i-2}$ 的时候，只有 $a_i-a_{i-1}$ 的前缀最小值才是有用的，可以双指针。

接下来考虑包含一个 $<t$ 的数，和两个 $\ge t$ 的数。

而且可以发现，一个最小值（$<t$ 的数）要能有用，必须满足区间包含了这块中的不超过 $2$ 个数。那么我们枚举最小值，对应的区间总长度是 $O(n\log v)$ 的。

算法 1

这是暴力。

显然这两个数只能在块 $t$ 和 $t+1$ 中，不妨判掉一个在 $t$ 一个在 $t+1$ 中的情况。然后需要解决的就是最大值和次大值同块的情形。

可以发现，如是在做这样一个事情：找到一个最小的 $x$，使得区间中存在两个数 $a_i,a_j\le x$，满足 $|a_i-a_j|<t$。

那么把块中的数排序，从小到大加入。类似区间最近点对，考虑加入一个 $a_p$ 带来的有贡献的对子，不妨设 $i<j<p$，如果 $(i,p)$ 和 $(j,p)$ 都有贡献，那么 $a_i>\frac {a_j+a_p} 2$。那么加入一个 $a_p$ 会带来 $O(\log v)$ 个新对子。找这个对子可以 $O(n\log n\log v)$ 线段树二分。

然后枚举最小值，找到这个最小值区间中的对子，可以发现这样找到了 $O(n\log^2 v)$ 个支配三元组。

然后用迭代分块进行二维数点。时间复杂度 $O(n\log^2 v+qn^{\epsilon})$，常数较小。

算法 2

可以证明，支配三元组数量是 $O(n\log v)$ 的（proved by ZhouKangyang）：

记枚举的最小值是 $x$，考虑这个最小值的区间，记 $b_i=\lfloor a_i/x\rfloor$，那么如果 $b_i=b_j$，那么 $a_i,a_j,x$ 必然是合法三角形。那么对于每类 $b_i$，相当于最小化区间 $a_i+a_j$，这非常经典，直接单调栈求出即可。另一类情况是 $|b_i-b_j|=1$，那么只需要对每个 $b_i$ 求出其前面和后面第一个 $b_j=b_i-1$（显然如果有 $k<j<i$ 使得 $b_k=b_j=b_i-1$ 那么 $(j,k)$ 更优）。

所以，支配三元组数正比于区间长度。

那么时间复杂度为 $O(n\log v\log n+q\log v)$（利用 veb 数点并 $O(n\log v)$ 求支配三元组可以更优，找支配三元组精细实现可以不用 hash），非常接近区间最近点对。常数较大。

十分遗憾地，根据我的实现，两种做法均可通过，但算法 1 的运行速度更快。