题解：P12084 [Ynoi1998] ZYPRESSEN

wwwwwza · 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)。

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

想要的可以私信问我。