考虑用f[i][j]表示以i为起点（i是时间，所以要离散）选$2^j$条线段（这里不是时间）最小的终点，预处理用倍增的方式来求即可
预处理出这个数组后，就可以很快的求出在$[l,r]$的时间内最多能选多少条线段，类似于树上的倍增（注意判断超过最大时间的情况）
然后从前往后枚举每一段时间，考虑能否加入，当且仅当其分割的那个区间的两部分的答案之和+1=原区间的答案，找区间可以用两个set（分别维护起点和终点）来搞

1 #include
2 using namespace std;
3 #define N 200005
4 struct ji{
5 int l,r;
6 bool operator < (const ji &k)const{ 7 return (ls1,s2;
11 int n,m,b[N<<1],f[N<<1][21]; 12 void build(){ 13 memcpy(aa,a,sizeof(a)); 14 sort(aa+1,aa+n+1); 15 aa[n+1].l=aa[n+1].r=m+1; 16 for(int i=1,j=1;i<=m;i++){ 17 while (i>aa[j].l)j++;
18 f[i][0]=aa[j].r;
19 }
20 for(int i=m-1;i;i--)f[i][0]=min(f[i][0],f[i+1][0]);
21 for(int i=0;i<=20;i++)f[m+1][i]=m+1; 22 for(int j=1;j<=20;j++) 23 for(int i=1;i<=m;i++)f[i][j]=f[min(m,f[i][j-1])+1][j-1]; 24 } 25 int query(int l,int r){ 26 int ans=0; 27 for(int i=20;i>=0;i--)
28 if (f[l][i]<=r){ 29 l=min(m,f[l][i])+1; 30 ans+=(1<a[i].l)||(*--s2.end()<a[i].r))continue;
54 int x=*--s1.upper_bound(a[i].l),y=*s2.lower_bound(a[i].r);
55 if ((x!=*--s1.end())&&(*s1.upper_bound(a[i].l)<=y))continue;
56 if (query(x,y)==query(x,a[i].l-1)+1+query(a[i].r+1,y)){
57 if (a[i].r==y)s2.erase(y);
58 else s1.insert(a[i].r+1);
59 if (a[i].l==x)s1.erase(x);
60 else s2.insert(a[i].l-1);
61 if (flag)printf(" ");
62 flag=1;
63 printf("%d",i);
64 }
65 }
66 }