【题解】Solution Set - NOIP2024集训Day14 CDQ分治
https://www.becoder.com.cn/contest/5482
「CF364E」Empty Rectangles
*3000 摆烂了。
「SDOI2011」拦截导弹
CDQ的例题，之前做过（现在试图自己再做出来。
第二问只用在第一问里面记录每一次是从哪个 \(j\) 转移过来的，以及当前位的方案数就行了。
看了之前的代码，发现其实还不止，这里其实还需要乘上后面的方案数。
也就是说，可能性 = (前方案数 \(\times\) 后方案数) \(\div\) 总方案数
下对于第一问考虑 dp。
\(f_i\) 前 \(i\) 个，钦定拦截第 \(i\) 个能拦截的最多个数。
令：\(f_0=0,h_0=\inf,v_0=\inf\)。
有转移：
\[f_i=\max_{0\le j<i\wedge h_j>h_i\wedge v_j>v_i}f_j+1 \]显然一个三维偏序（还有一维下标），考虑用 CDQ 将 dp 优化到 \(O(n\log^2n)\)。
试着用残余的记忆，自己重新把三维偏序胡出来。下面是口嗨时间。
回忆一下 CDQ 的步骤：
-
先把大于等于
mid的 \(h\) 分到左边，小于的分到右边。（实际上这一维最好以下标分开（这样就不用stable_partition了。考虑把左边的部分按照 \(h\) 重新排序。
（口胡不下去了（因为感觉怪怪的就去看了一下之前的代码，感觉还是挺好理解，所以就不想写了（
所以下一个任务是在 15min 之内爆切 cdq（雾
标签：Set,题解,Solution,Day14,CDQ,NOIP2024 From： https://www.cnblogs.com/CloudWings/p/18375427