题目概述

在一个长为 $m$ 的环上有 $n$ 个线段 $(s_i,t_i)$ ，在线段不交的情况下最多选择多少个线段？

解题报告

思路还停留在以前的斯波解法上……然后gg……没环的话可以有三种做法：1.DP。2.贪心。3.贪心+倍增。不过因为没环所以第三种倍增是没有意义的。

但是有环的话前两种都不能用了，现在我们先考虑环断链，然后线段有两种情况：

1. $s<t\to (s,t),(s+m,t+m)$ 。
2. $s>t\to (s,t+m)$ 。

现在的问题转化为选出一个长为 $m$ 的区间使得能够选出的左右端点均在该区间的线段最多，一个区间可以做贪心：目前最右边的线段为 $(S,T)$ ，那么下次选的一定是所有 $s_i\ge T$ 中 $t_i$ 最小的。但每个区间里贪心一遍是不可能的，这时候倍增快速跳就有用处了。

示例程序

#include<cstdio>
#include<algorithm>
#define fr first
#define sc second
#define mp make_pair
using namespace std;
const int maxn=200000,Log=18;

int m,n,MIN[maxn+5],ST[maxn+5][Log+5],ans;pair<int,int> s[maxn+5];

inline int Miner(int x,int y) {return s[x].sc<s[y].sc?x:y;}
inline int Find(int L,int R,int x){
    for (int mid=L+(R-L>>1);L<=R;mid=L+(R-L>>1))
        s[mid].fr>=x?R=mid-1:L=mid+1;return MIN[L];
}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    int N;scanf("%d%d",&m,&N);
    for (int i=1;i<=N;i++){
        int x,y;scanf("%d%d",&x,&y);
        if (x>y) s[++n]=mp(x,y+m); else s[++n]=mp(x,y),s[++n]=mp(x+m,y+m);
    }
    sort(s+1,s+1+n);MIN[n]=n;for (int i=n-1;i;i--) MIN[i]=Miner(MIN[i+1],i);
    for (int i=n;i;i--){
        ST[i][0]=Find(i+1,n,s[i].sc);
        for (int j=1;j<=Log;j++) ST[i][j]=ST[ST[i][j-1]][j-1];
    }
    for (int i=1;i<=n;i++){
        int R=i,num=1;
        for (int j=Log;~j;j--) if (ST[R][j]&&s[ST[R][j]].sc<=s[i].fr+m) R=ST[R][j],num+=1<<j;
        ans=max(ans,num);
    }
    return printf("%d\n",ans),0;
}