APIO2009 会议中心
题意：
给你 \(n\) 条线段，第 \(i\) 条线段的编号是 \(i\)。
你需要按顺序取出一些线段，使其两两不交。
你要求出最大可以取出多少条线段，并求出字典序最小的方案。
数据范围：\(n \le 2 \times 10^5,1 \le l_i \le r_i \le 10^9\)。
思路：
首先考虑第一问，这是经典的贪心问题。
按照右端点排序，然后能选就选即可。
原因也很简单，如果当前不选这个线段，那把之后取的第一线段换成这个线段一定还是可行。
令求出的第一问的答案是 \(ans1\)。
令 \(pos_i\) 表示线段 \(i\) 排完序后的编号。
定义一个集合是合法的当且仅当其能够通过扩充线段达到一个大小为 \(ans1\) 且线段两两不交的集合。
令 \(f(i,j)\) 为线段 \(i\) 和线段 \(j\) 之间最多能取的线段个数。（排完序的下标）
那一个集合 \(\{s_1,s_2,\cdots,s_m\}\) 是合法的的充要条件是：（假设我们强制插入了最小区间 \([-10^9,-10^9]\) 和最大区间 \([10^9+1,10^9+1]\)）
\[m+\sum_{i=1}^{m-1} f(s_i,s_{i+1})-2=ans1 \]令 \(ans2\) 为答案集合。
我们从 \(1\) 到 \(n\) 枚举线段 \(i\)（没排序的编号），依次判断其加入答案集合后是否合法。
显然，若加入后集合合法，那不选这条线段一定不优，而若不合法，那显然不能加入。
二分出 \(ans2\) 中 \(i\) 的前一个线段 \(last\) 和后一个线段 \(next\)。（排完序后的下标）
那充要条件就是 \(f(pos_{last},pos_{next})=f(pos_{last},pos_i)+f(pos_i,pos_{next})+1\)。
现在的问题就是如何快速计算 \(f(i,j)\)。
考虑取的第一个位置一定是排序后第一满足 \(r_i<l_x\) 的线段。
然后取了第 \(x\) 个线段（排序后的下标）后取的下一个线段取排序后第一个满足 \(r_x < l_y\) 的线段 \(y\) 一定不劣。
考虑到起点确定，每一步确定，且不因 \(i,j\) 而改变，因此直接倍增即可。
时间复杂度 \(\Theta(n\log {n})\)。
标签：10,le,线段,pos,大战,排序,集合,APIO From： https://www.cnblogs.com/zzzYheng/p/16877620.html