题解 ZYPRESSEN

· · 题解

首先把值域按照 [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 的运行速度更快。