这题和 \(bzoj4444\) 差不多吧。

倍长之后,要求长度为 \(m\) 的所有区间的答案。

倍增就好啦,\(f(i,j)\) 表示,从 \(i\) 开始,往右取 \(2^j\) 个区间,需要的右边界的最小值。

这样就是 \(O(n \log n)\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include<cstdio>
#include<cstring>
#include<algorithm>
#define X first
#define Y second
#define mp make_pair
using namespace std;
const int maxn=400005;
pair<int,int> a[maxn];
int n,m,K,f[maxn][20],ans;
int b[maxn];
int Find(int x){
return lower_bound(b+1,b+1+b[0],x)-b;
}
int main(){
scanf("%d%d",&m,&n);
for(int i=1;i<=n;i++){
int x,y; scanf("%d%d",&x,&y);
if(x>y) y+=m;
a[++K]=mp(x,y); a[++K]=mp(m+x,m+y);
}
for(int i=1;i<=K;i++) b[++b[0]]=a[i].X, b[++b[0]]=a[i].Y;
sort(b+1,b+1+b[0]); b[0]=unique(b+1,b+1+b[0])-b-1;
b[b[0]+1]=2e9;
for(int i=0;i<=19;i++) f[b[0]+1][i]=b[0]+1;
for(int i=1;i<=b[0];i++) f[i][0]=b[0]+1;
for(int i=1;i<=K;i++){
a[i].X=Find(a[i].X); a[i].Y=Find(a[i].Y);
f[a[i].X][0]=min(f[a[i].X][0],a[i].Y);
}
for(int i=b[0]-1;i>=1;i--) f[i][0]=min(f[i][0],f[i+1][0]);
for(int i=1;i<=19;i++)
for(int j=1;j<=b[0];j++)
f[j][i]=f[f[j][i-1]][i-1];
for(int i=1;i<=b[0];i++){
int x=i,res=0;
for(int j=19;j>=0;j--)
if(b[f[x][j]]<=b[i]+m) x=f[x][j], res+=(1<<j);
ans=max(ans,res);
}
printf("%d\n",ans);
return 0;
}