【关键字】偏序，数点，树状数组，线段树，扫描线。

因为涉及多种算法，所以整合到一起。

【扫描线】

二维数点，偏序

★数点问题

★关于偏序问题的一些总结

一维偏序：排序二分　　树状数组

二维偏序：排序扫描线+树状数组(差分)/线段树

三维偏序：排序扫描线+cdq分治+树状数组　　排序扫描线+二维数据结构

基本思想是一维扫描线顺序扫描维护差分，一维用数据结构维护区间（线段树维护区间，树状数组差分维护前缀和）。

[BZOJ3161]布娃娃（扫描线+线段树）

BZOJ 4059 Cerc2012 Non-boring sequences 线段树+扫描线

矩阵面积并

hdu 1542 扫描线+线段树求矩阵面积并

线段树辅助——扫描线法计算矩形面积并

例题：

【STSRM13】绵津见 二维偏序，排序+树状数组

【链与反链】

引用自：最长反链与最小链覆盖 by vfleaking

链是点的集合，这个集合中任意两个元素v、u，要么v能走到u，要么u能走到v。

反链是点的集合，这个集合中任意两点谁也不能走到谁，可以理解为有向边取反后的链。

★最小链覆盖=最长反链

最小反链覆盖=最长链

经典模型：最少严格递减子序列覆盖=最长不严格递增子序列

　　　　　最少不严格递增子序列覆盖=最长严格递增子序列（链与反链的互补关系）

不严格证明：从二分n log n求LIS的过程中可以得到一组合法解。

二分求解LIS的原理是数字依次添加，缺数字加数(ans+1)，不缺数字替换掉第一个比它大(或等)的数字。

二分过程中一个位置被替换的所有数字（包括当前的数字）组成一个递减子序列，位置总数就是最长上升子序列。

这样替换的正确性在于：访问某位置时，其前面的位置一定存在数字在该位置之前（反证：若不存在，则一定会替换该位置），这样传递下去可以找到上升子序列。

View Code

最长上升子序列(LIS)本质上是二维偏序，要求满足a[i]<a[j]&&h[i]<h[j]的最长序列。

也可以视为二分图不交叉最大匹配(上帝选人)：一维排序（a[i]），一维可以树状数组维护DP，也可以二分。

链模型转化：对于所有满足满足a[i]<a[j]&&h[i]>h[j]的点i和点j连接有向边，最长链覆盖=最长反链。

NOIP 1999 导弹拦截

CTSC2008 祭祀

【专题】偏序，扫描线