题意：
给定一个序列，每个元素有两个属性 $h$ 和 $v$ ，是导弹的高度和速度，发射的拦截炮弹第一发可以是任意的高度和速度，但是要求每一发炮弹的高度和速度都不能大于前一发。问：
1. 选取最优的发射方案的时候最多能拦截多少发导弹
2. 当有多个拦截导弹数目相同的最优方案的时候，我方会从中随机选取一种方案，现在问在这种策略下，每发炮弹能拦截到导弹的概率是多少
题解：
第一问很明显使用cdq分治加速dp转移算LIS，难点在于第二问。把LIS各个节点的转移看成图上的连边的话，可以得到一个dag，而后可以想见使用dp求出到每个点的在LIS上的路径有多少条，便可以确定随机选取的情况下每个节点被选取到的概率为 经过该点的在LIS上的路径数/所有的在LIS上的路径数 。判断一个点是否在LIS上，我们可以两端各求一次LIS，分别记为 $dpl[i] dpr[i]$ ,则如果当前节点满足 $dpl[i]+dpr[i]=\max\limits_{1\le j\le n} dpl[j]+1$ 则说明其属于某个LIS，+1是为了去除节点本身的重复计算。 为了求出经过某个点的路径数，我们可以用之前 dp求最短路必经边的方法 ，从两端分别跑一次dp，分别记录两端到某个节点的属于LIS的路径数为 $gl[i]\;gr[i]$ ，这样的话经过节点i的路径数就可以表示为 $gl[i]*gr[i]$ ，则每个点被选中的概率就可以被表示为
$$\frac{gl[i]*gr[i}{\sum_{[dpl[k]=LIS]}gl[k]}$$
这就是第二问的答案了。因为分治中每次需要对 $[l,r]$ 之间的元素暴力排序，所以复杂度会多一个 $log$ ，也就是 $\mathcal{O}(n\log{}n)$
继续阅读“[DP][CDQ分治][树状数组] bzoj2244 SDOI2011 拦截导弹”