[APIO2009]会议中心 标题问题大意：
原网址与样例戳我!
给定n个区间，询问以下问题：
1.最多能够选择几多个不订交的区间？
2.在第一问的根本上，输出字典序最小的方案。
数据范畴：\(n \leq 2\times 10^5\)
对付字典序最小的结构题，一个套路：
以字典序从小到大枚举，依次查抄每个元素是否可以计入答案。
然后是两个函数的辨析：
\(lower\_ bound(x)\)：返还第一个大于即是\((\ge)\)\(x\)的位置。
\(upper\_bound(x)\)：返还第一个严格大于\((>)\)\(x\)的位置。
\(Tag\)：贪心 + 倍增 + \(set\)
A先去失包罗关系，原因略，此时摆布端点都是递增的了。
第一问的确弱智，贪心的入门题，这里不说了，关键在于字典序最小方案如何输出。
考虑上文中说到的阿谁套路：
以字典序从小到大枚举每一条线段，判断插手这条区间后答案是否会变差。
如果答案不会变差，那么必定就优先选择这个区间了。
下面我们来看如何判断插手区间后答案是否变差。
我们令\(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]\)的右边的阿谁区间的左端点。
由上文可知，我们枚举区间，每次得到\(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\)，先二分找到范畴内第一个区间，然后倍增求解即可。
梗概思路就这样，本题的实现上也有必然的难度。
风闻可以用线段树或\(splay\) , 横竖我使用的是\(set\)来求解。
在畴前往后扫的过程中，我们用\(set\)来生存已经插手答案的区间调集。
\(set\)中的区间以右端点为优先级排序，每次找影响范畴\(l\ ,\ r\)直接在\(set\)里二分即可。
然后注意得到\(lp\ ,\ rp\)后要判交，如果交了也要\(continue\)。
细节上，计算\(f(lp,rp)\)的时候注意判断答案为0的情况，，\(nxt[i][0]\)也可以二分求解。
注：\(q[i]\)为标题问题给定的原区间序列 ， \(t[i]\)为去重、以左端点排序后的新区间序列。
#include<bits/stdc++.h> #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< int > ans ; struct node{ int l , r ; IL bool operator < (const node &B)const{ return r < B.r ; } }; node t[_] , q[_] ; set< node > S ; set< node >::iterator t1 ,t2 ; IL bool cmp(node a , node b){return (a.l==b.l)?a.r>b.r : a.l<b.l ;} IL void Prepare(){; for(RG int i = 1; i <= n; i ++) xx[ i ] = t[ i ].l ; xx[ n + 1 ] = inf ; tot1 = n + 1; for(RG int i = 1; i <= n; i ++) f[ i ][ 0 ] = upper_bound(xx+1,xx+tot1+1,t[ i ].r) - xx ; for(RG int i = 1; i <= n; i ++) if(f[ i ][ 0 ] == n + 1)f[ i ][ 0 ] = 0 ; for(RG int j = 1; j <= 19 ; j ++) for(RG int i = 1; i <= n; i ++) f[ i ][ j ] = f[ f[ i ][ j - 1 ] ][ j - 1 ] ; return ; }//f[i][j] 暗示从i开始(不算i)向后选择2^j个区间,最后一个为第f[i][j]个区间. IL void Pre(){ cin >> n ; N = n ; tot1 = 0 ; tot = 0; for(RG int i = 1,l,r; i <= n; i ++) cin >> q[i].l >> q[i].r ; for(RG int i = 1; i <= n; i ++) t[ i ].l = q[ i ].l , t[ i ].r = q[ i ].r; sort(t + 1 , t + n + 1 , cmp ) ; t[ ++ tot ] = t[ 1 ] ; for(RG int i = 2; i <= n; i ++){ while(t[ i ].r <= t[ tot ].r && tot) -- tot ; t[ ++ tot ] = t[ i ] ; }// 去重 n = tot ; Prepare() ; } IL int Calc(RG int L , RG int R){ RG int c = lower_bound(xx + 1, xx + n + 1 , L) - xx; if(R < L || t[c].r > 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 <= R) c = f[ c ][ i ] , res |= (1 << i) ; return res + 1 ; //记得加上范畴内的第一个区间 } int main(){ std::ios::sync_with_stdio(false) ; Pre() ; S.insert( (node){-inf , -inf} ) ; S.insert( (node){inf , inf} ) ; Ans = Calc(-inf , inf) ; for(RG int i = 1; i <= N; i ++){ t2 = S.lower_bound( q[ i ] ) ; t1 = t2 ; t1 -- ; lp = (*t1).r ; rp = (*t2).l ; if(lp >= q[i].l || rp <= q[i].r) continue ; //判交 lp ++ ; rp -- ; s1 = Calc(lp , q[i].l - 1) + Calc(q[i].r + 1 , rp) + 1; s2 = Calc(lp , rp) ; if( ! (s1 ^ s2) ) ans.push( i ) , S.insert( q[ i ] ) ; } cout << Ans << endl; while(!ans.empty())printf("%d ",ans.front()) , ans.pop() ; return 0; }