czp 代码太史了我发个不史的.

思路大致相同

upd:他改代码了没事了

#include<bits/stdc++.h>
#define int long long
#define R(x) x=read()
using namespace std;
inline int read() {
	int x=0,y=1;
	char e=getchar();
	while(e>'9'||e<'0') {
		if(e=='-')y=-1;
		e=getchar();
	}
	while(e>='0'&&e<='9') {
		x=(x<<3)+(x<<1)+(e^'0');
		e=getchar();
	}
	return x*y;
}
const int N=400005;
int n,m;
struct node {
	int l,r,id;
} a[N];
bool cmp(node A,node B) {
	return A.l<B.l;
}
int nxt[N][25];
int ans[N];
signed main() {
	R(n),R(m);
	for(int i=1; i<=n; ++i) {
		R(a[i].l),R(a[i].r),a[i].id=i;
	}
	sort(a+1,a+1+n,cmp);
	for(int i=1; i<=n; ++i) {
		if(a[i].r<a[i].l)a[i].r+=m;
		a[i+n].l=a[i].l+m,a[i+n].r=a[i].r+m,a[i+n].id=a[i].id;
	}
	for(int i=1,j=1; i<=(n<<1); ++i) {
		while(j+1<=(n<<1)&&a[i].r>=a[j+1].l)
			++j;
		nxt[i][0]=j;
	}
	for(int j=1; j<=log2(n*2); ++j)
		for(int i=1; i<=n*2; ++i)
			nxt[i][j]=nxt[nxt[i][j-1]][j-1];
	for(int i=1; i<=n; ++i) {
		int cnt=0,nw=i;
		for(int j=log2(n*2); j>=0; --j)
			if(a[nxt[nw][j]].r<a[i].l+m)
				cnt+=(1<<j),nw=nxt[nw][j];
		ans[a[i].id]=cnt+1+1;
	}
	for(int i=1; i<=n; ++i) cout<<ans[i]<<" ";
	return 0;
}

由于第一个和最后一个没有算，所以最后加2

题意

有一个长度为m的环，有n条线段，问一定选第i条线段时，要至少选多少条线段可以使得整个环都被覆盖

性质

任意一条线段不会被另一条线段完全包含，所以只要一条线段的左端点大于另一条边的左端点，那么这一条线段的又端点一定大于另一条线段的右端点。

暴力

知道了这个性质之后就可以贪心了， 如图，如果我们已经选了红色线段，那么选蓝色线段一定比绿色线段更优，即新选择的左端点要尽可能大但是要小于等于之前那条线段的右端点。 这样可以枚举每一个必选的线段，然后暴力遍历所有线段贪心出答案 时间复杂度$O(n^2)$

正解

st表 如果我们暴力枚举每一条线段，他的复杂度是$O(n)$,我们注意到每条线段的下一条最优线段是好求的，然后将两个线段的答案合并也是好求的，所以我们可以想到st表倍增求解

upd

如果你是暴力算st表的0次方，会t掉一个点，考虑l,r的单调性，它或许可以用双指针求解。

注意排序后要存原本的下标。

破环成链：

if(arr[i].r < arr[i].l) arr[i].r += m;
arr[i+n] = arr[i];
arr[i+n].l += m;
arr[i+n].r += m;

code:

#include <bits/stdc++.h>
using namespace std;

const int N = 500000;

int n, m;
struct node {
	int l, r, id;
	friend bool operator < (node a,node b) {
		return a.l < b.l;
	}
}mp[N];

int ans[N], st[N][20];

int log2(int x) {
	int ans = 0;
	while((1 << ans) <= (x >> 1)) ans++;
	return ans;
}

int find(int i) {
	int aim = mp[i].l + m, cur = i, nxt, ans = 1;
	for(int p = log2(n); p >= 0; p--) {
		nxt = st[cur][p];
		if(nxt != 0 && mp[nxt].r < aim) {
			ans += 1 << p;
			cur = nxt;
		}
	}
	return ans + 1;
}

void read() {
	scanf("%d %d",&n,&m);
	for(int i = 1; i <= n; i++) {
		scanf("%d %d",&mp[i].l,&mp[i].r);
		if(mp[i].l > mp[i].r) mp[i].r += m;
		mp[i].id = i;
	}
}

void compute() {
	sort(mp+1,mp+1+n);
	for(int i = 1; i <= n; i++) {
		mp[i+n] = mp[i];
		mp[i+n].l += m;
		mp[i+n].r += m;
	}
	int ww = n << 1;
	for(int i = 1,j = 1; i <= ww; i++) {
		while(j + 1 <= ww && mp[j+1].l <= mp[i].r) j++;
		st[i][0] = j;
	}
	int nn = log2(n);
	for(int p = 1; p <= nn; p++) {
		for(int i = 1; i <= ww; i++) {
			st[i][p] = st[st[i][p-1]][p-1];
		}
	}
	for(int i = 1; i <= n; i++) {
		ans[mp[i].id] = find(i);
	}
	for(int i = 1; i <= n; i++) printf("%d ",ans[i]);
}

int main() {
	read();
	compute();
	return 0;
}