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

lzyqwq · 2024-11-23 20:44:23 · 题解

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 最小值。

考虑按照二进制最高位将值域划分成若干个块，记 B_m=[2^m,2^{m+1})。设值域为 V。

显然不用考虑 (i,j,k) 之间的大小关系，只要求她们不同且都在区间里面就一定可以将三元组写成递增的形式。注意到同块中任意三个元素均能作为三角形边长，因此对于每个询问，考虑找到最小的 m 使得 (a_l,\dots,a_r) 在 B_m 中有 \ge3 个元素。此时选取前三小值即可。线段树维护之，合并可以看成左右儿子信息归并。

这里可以考虑从小到大枚举每个块，再枚举询问，更新所有未被标记且在她中有 \ge 3 个元素的询问，然后标记这个询问。每个询问至多被标记一次，这时才会触发查询，因此时间复杂度为 \mathcal{O}(q\log n)。

对于剩下的方案，如果想要更优，则必须至少存在一个 <2^k 的元素。判断区间中某块内的元素个数可以先预处理该块内元素的前缀出现次数然后前缀相减。枚举每个块时都要处理一次，时间复杂度为 \mathcal{O}(n\log |V|)。

• 若存在 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 的最小值，直接扫描线配合树状数组维护即可。

到这里基本结束了。时间复杂度为 \mathcal{O}((n\log |V|+q)\log |V|)，空间复杂度为 \mathcal{O}(q\log |V|+|V|)。如果扫描线时使用高级点的数据结构可以做到更优时间复杂度。空间带 |V| 的原因是对于每种 e_k 开了单调栈，如果离散化可以做到更优。

然后我的实现被卡常了，加了指令集也会不时被卡。联系出题人要求时限增大 0.5\text{ s} 未果。建议被卡常的找个夜深人静的时候多交几发试试。

AC Link / Code