过了几个月，又回来了，3.7 之前的懒得补了。
3.7
P2487 [SDOI2011] 拦截导弹
最近在学 CDQ。花了我好久调试。
CDQ 优化 DP 模板。
将转移条件转化成三维偏序。在 CDQ 中求。至于每个点在最长的二维最长升子序列的出现次数，多开一个数组 \(f[0/1][i]\) 存，转移还是使用树状数组顺带做了。\(0/1\)，表示以此点为开头或结尾。
最后如果 \(dp[0][i] + dp[1][i] = len + 1\) 则这个点答案为 \(f[0][i] * f[1][i] / sum\)。
P3834 可持久化线段树 2
顺带用整体二分做了一个板子题。感觉这个算法好 NB。
P4093 [HEOI2016/TJOI2016] 序列
一开始连题都看错了。描述不清的题面，SM 的出题人。或许是我是个 SB。
开了题解才明白题目。是我大意了。
也是一道很板的 CDQ 优化 DP。但以后一定要注意，转移时是 dp[a[i].id] 而不是 dp[i]。（-1h。
P3364 Cool loves touli
板子 +1。
注意开 long long，然后再离散化。树状数组与离散化数组大小开 \(3 \times N\)。我在这里 WA 了一发。
P4390 [BalkanOI2007] Mokia 摩基亚
简单板子。将查询分为四个点每次求 0,0 到 x,y 的一个矩形中的总权值。
相当于求 \(x_i \le x_j \land y_i \le y_j \land t_i \le t_j\) 的 \(a_i\) 总和。三维偏序，可以使用 CDQ 维护它。
注意树状数组上界一定要开大，不然会少加上数！
标签：le,树状,板子,CDQ,数组,月杂,题记,dp From： https://www.cnblogs.com/luckycloud/p/18057578