[APIO2009]会议中心

题目大意：

原网址与样例戳我!
给定n个区间，询问以下问题：

• 1.最多能够选择多少个不相交的区间？
• 2.在第一问的基础上，输出字典序最小的方案。
  数据范围：\(n \leq 2\times 10^5\)

前言：几个小 \(tips\)

对于字典序最小的构造题，一个套路：
以字典序从小到大枚举，依次检查每个元素是否可以计入答案。
然后是两个函数的辨析：

\(lower\_ bound(x)\)：返还第一个大于等于\((\ge)\)\(x\)的位置。
\(upper\_bound(x)\)：返还第一个严格大于\((>)\)\(x\)的位置。

正文：解法与思路

\(Tag\)：贪心 + 倍增 + \(set\)

A

先去掉包含关系，原因略，此时左右端点都是递增的了。
第一问简直弱智，贪心的入门题，这里不说了，关键在于字典序最小方案如何输出。
考虑上文中说到的那个套路：

以字典序从小到大枚举每一条线段，判断加入这条区间后答案是否会变差。

如果答案不会变差，那么肯定就优先选择这个区间了。
下面我们来看如何判断加入区间后答案是否变差。

B

我们令\(f(lp,rp)\)表示在\([lp,rp]\)这个区间内最多可以选择的区间个数。
那么，假设我们把区间\([l_0,r_0]\)插入，
如果答案不会变差，对于所有的区间\([lp',rp']\)，应该都有：
\[f(lp',rp') = f(lp',l_0-1) + f(r_0+1,rp') + 1\]
自己yy一下即可。
显然，加入区间\([l_0,r_0]\)的影响范围是有限的，我们可以发现这个范围为：
左边界 \(lp\)：已经加入的区间中，在\([l_0,r_0]\)的左边的那个区间的右端点。
右边界 \(rp\)：已经加入的区间中，在\([l_0,r_0]\)的右边的那个区间的左端点。

C

由上文可知，我们枚举区间，每次得到\(lp\ ,\ rp\)，然后需要判断上面的等式是否成立。
如果成立，则把此区间加入答案集合中，否则\(continue\)。
给定\(lp\ ,\ rp\) , 如何快速求\(f(lp,rp)\)呢？ 考虑倍增。
把原区间序列按左端点排序，得到一个新区间序列，
令\(nxt[x][d]\) 表示从第\(x\)个区间向后选择\(2^d\)个区间(不包括\(x\))，最后一个区间为\(nxt[x][d]\)。
转移显然：\(nxt[x][d] = nxt[\ nxt[x][d-1]\ ][d-1]\)。
有了\(nxt\)数组后，每次给定\(lp\ ,\ rp\)，先二分找到范围内第一个区间，然后倍增求解即可。

D

大体思路就这样，本题的实现上也有一定的难度。
听说可以用线段树或\(splay\) , 反正我使用的是\(set\)来求解。
在从前往后扫的过程中，我们用\(set\)来保存已经加入答案的区间集合。
\(set\)中的区间以右端点为优先级排序，每次找影响范围\(l\ ,\ r\)直接在\(set\)里二分即可。
然后注意得到\(lp\ ,\ rp\)后要判交，如果交了也要\(continue\)。
细节上，计算\(f(lp,rp)\)的时候注意判断答案为0的情况，\(nxt[i][0]\)也可以二分求解。

实现代码：

注：\(q[i]\)为题目给定的原区间序列 ， \(t[i]\)为去重、以左端点排序后的新区间序列。

#include
#define RG register
#define IL inline
#define inf 1e9+7
#define _ 200005
using namespace std;

int xx[3*_] , f[_][20] ,N,n,m,tot1,tot,lp,rp,s1,s2;
int Ans ;  queue ans ;
struct node{
    int l , r ;
    IL bool operator  S ; set::iterator t1 ,t2 ; 

IL bool cmp(node a , node b){return (a.l==b.l)?a.r>b.r : a.l> n ; N = n ; tot1 = 0 ; tot = 0;
    for(RG int i = 1,l,r; i > q[i].l >> q[i].r ;
    for(RG int i = 1; i  R || c > n) return 0 ;
    RG int res = 0;
    for(RG int i = 19; i >= 0 ; i --)
        if(f[ c ][ i ]  && t[ f[ c ][ i ] ].r = q[i].l || rp