专栏文章

知不可乎骤得，托遗响于悲风。

llzyqwq
P11364题解参与者 22已保存评论 25

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
25 条
当前快照
1 份
快照标识符
@miqx0d7i
此快照首次捕获于
2025/12/04 12:07
3 个月前
此快照最后确认于
2025/12/04 12:07
3 个月前
查看原文
感谢这题给我送退役了。
题意很简洁了，这里不再概括。
考虑到 dfn\text{dfn} 最小值和最大值两个点求一下 LCA\text{LCA} 的做法和我一样没有前途，因此换一条路冲，注意到一个结论：
记 ai=depLCA(i,i+1)a_i=\text{dep}_{\text{LCA}(i,i+1)}，则当 l≠rl\ne r 时 depLCA∗(l,r)=min⁡i=lr−1ai\text{dep}_{\text{LCA}^*(l,r)}=\min\limits_{i=l}^{r-1}a_i。
证明：
  • 随着区间的扩展 LCA\text{LCA} 深度一定不升，因此 LHS≤RHS\text{LHS} \le \text{RHS}。
  • 考虑区间 LCA=x\text{LCA}=x，则一定存在区间内两个点 i,j(i<j)i,j(i<j) 来自于 xx 的不同子树。此时 [i,j)[i,j) 中一定存在一个位置 pp 满足 pp 和 p+1p+1 来自不同子树，则 apa_p 会取到 depx\text{dep}_x。
因此把 k=1k=1 的询问判掉之后，令 r←r−1,k←k−1r\leftarrow r-1,k \leftarrow k-1。则问题变成求一个子区间 [l′,r′]⊆[l,r][l',r']\sube [l,r] 满足 r′−l′+1≥kr'-l'+1\ge k 且区间最小值最大。
O(nlog⁡2n)\mathcal{O}\left(n\log^2 n\right) 已经随便做了，但我们姑且认为她是过不了的。
考虑枚举答案 vv，找到所有 ai≥va_i\ge v 的极长连续段，则只要询问区间 [l,r][l,r] 和极长连续段交集对应的区间长度 ≥k\ge k，那么答案就可以 ≥v\ge v。因此答案是最大的 vv 使得存在一个 ai≥va_i\ge v 的极长连续段 [l′,r′][l',r'] 和 [l,r][l,r] 的交集区间长度 ≥k\ge k。
极长连续段可以这样找：从大到小加入 aia_i，每次尝试和左右相邻的极长连续段合并。这样一定会找到极长连续段，还会找到一些非极长的。但是没关系，跟非极长交出来区间长度 ≥k\ge k 则和极长的交出来的区间长度也一定 ≥k\ge k。这个过程可以 set 维护。
此时如果你考虑两个区间的关系为包含、被包含、左边相交、右边相交四类，会搞出三维偏序来，无法接受。但是可以不这么拆。
考虑将答案分成以下有重叠且并集为全集的部分，重叠显然不影响最大值：
  • l≤l′l\le l'。
  • r≥r′r\ge r'。
  • l′≤l≤r≤r′l'\le l\le r\le r'。
第三种交集是整个区间肯定合法，因此是求这个范围内的极长连续段的 vv 最大值，扫描线 + BIT 维护即可。
至于前两种是类似的，以第一种为例。
此时要求 l′∈[l,r−k+1]l'\in[l,r-k+1] 才能交出长度 ≥k\ge k 的子区间。我们发现剩下仅需要满足 r′−l′+1≥kr'-l'+1\ge k 就够了。这个是充要的，可以讨论 r′,rr',r 的大小关系证。
那么看成关于 l′l' 和 r′−l′+1r'-l'+1 两维的二维偏序即可。由于是 3−side3-\text{side} 因此用线段树 + 扫描线维护。
时间复杂度为 O(nlog⁡n)\mathcal{O}(n\log n)，空间复杂度为 O(n)\mathcal{O}(n)。
AC Link & Code
知不可乎骤得，托遗响于悲风。你不能只在进省队的时候才热爱 OI。你不能只在切出 DS 的时候才热爱 DS。

评论

共 25 条评论，欢迎与作者交流。

正在加载评论...