题解：CF2165F Arctic Acquisition

nullqtr_pwp · 2025-11-22 19:48:05 · 题解

显然 [l,r] 合法一定有 [l-1,r],[l,r+1] 合法，这样求出来每个 l 最小的 r 合法即可，答案为 \sum n-f_i+1。

注意到子序列 21435 显然要拆开。固定 2 的位置 i，一定是找下一个 a_j<a_i,j>i 作为 1。放到坐标系 (i,a_i) 上，转化为 x\in[j+1,n],y\in[a_i+1,n] 的部分中的一个 213 子序列，范围即为一个 2-side 矩形。

考虑枚举这个子序列中 1 的位置 p，注意枚举 2 的话这里就会有很多 (2,1,3)，考虑枚举 3 的位置 q，如果并非 [p+1,n] 中的前缀 \max 那么就会被前面那个点支配掉。令 [p+1,n] 中所有前缀 \max 并且 >a_p 的位置分别为 r_1,r_2,r_3,\cdots。如果最终取的是 r_2,r_3 之类，那么取的 2 的值一定 >a_{r_1}，那么 p 可以移动到 r_1，并且范围更大，因此只需要考虑 a_{r_1} 为 3。对于 r_1 显然可以用单调栈找。此时找前缀最后一个落在 [a_p,a_{r_1}] 的点作为 2 即可。综上，只有 \mathcal O(n) 个有效的 213 子序列。

转化为：n 个带点权的点，查询的是 n 个 2-side 矩形内部点权 \min。容易扫描线解决，时间复杂度 \mathcal O(n\log n)。

提交记录