题目大意
分析
把环拆开
线段其实就是区间
对于每个区间，向在TA后面并且b_i最小的区间连边，
然后从每个区间(ai,bi)开始，在保证跳到的区间(aj,bj)，bj<=ai+m的情况下向后倍增。
#include <cmath>
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>
#include <bitset>
#include <set>
#include <vector>
const int inf=2147483647;
const int mo=1e9+7;
const int N=100005;
using namespace std;
struct arr
{
int x,y,be;
}a[N*2],b[N*2];
int n,m,g[N*2][25],mn[N*2],ans;
bool cmp(arr x,arr y)
{
return x.y<y.y || (x.y==y.y && x.x<y.x);
}
bool cmp1(arr x,arr y)
{
return x.x<y.x || (x.x==y.x && x.y<y.y);
}
int main()
{
scanf("%d%d",&m,&n);
for(int i=1;i<=n;i++)
{
scanf("%d%d",&a[i].x,&a[i].y);
if(a[i].x>a[i].y) a[i].y+=m;
a[i+n].x=a[i].x+m,a[i+n].y=a[i].y+m;
}
sort(a+1,a+1+n,cmp);
for(int i=1;i<=n*2;i++) b[i]=a[i],b[i].be=i;
sort(b+1,b+1+n,cmp1);
a[0].y=b[n*2+1].y=inf,mn[n*2+1]=n*2+1;
for(int i=n*2;i>=1;i--) mn[i]=b[i].y<b[mn[i+1]].y?i:mn[i+1];
for(int i=1,pos=1;i<=n*2;i++)
{
while(a[i].y>b[mn[pos]].x && pos<=n*2) pos++;
g[i][0]=b[mn[pos]].be;
}
for(int j=1;j<=20;j++)
for(int i=1;i<=n*2;i++) g[i][j]=g[g[i][j-1]][j-1];
ans=1;
for(int i=1;i<=n;i++)
{
int k=i,sum=0;
for(int j=20;j>=0;j--)
if(a[g[k][j]].y<=a[i].x+m) k=g[k][j],sum+=1<<j;
ans=max(ans,sum);
}
printf("%d",ans+1);
}