C++(g++ 7.5.0) 解法, 执行用时: 267ms, 内存消耗: 37652K, 提交时间: 2023-08-10 16:52:33

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 400010;
int n, m, f[17][N], ans[N / 2];
struct SECTION { int l, r, id; } s[N];
bool cmp(SECTION a, SECTION b) { return a.l < b.l; }
int query(int x) {
    int end = s[x].l + m, res = 0;
    // 从大到小倍增
    for (int i = 16, pos = x; i >= 0; i--)
        // 这里是小于号, 之后最后的区间统一 + 1 就好, 否则难以处理
        if (s[f[i][pos]].r < end)
            pos = f[i][pos], res += (1 << i);
    // 加上自己和下一个区间
    return res + 2;
}
signed main() {
    cin >> n >> m;
    // 复制一倍接到后面
    for (int i = 1; i <= n; i++) { 
        cin >> s[i].l >> s[i].r;
        if (s[i].r < s[i].l) s[i].r += m;
        s[i + n].l = s[i].l + m, s[i + n].r = s[i].r + m;
        s[i].id = i, s[i + n].id = i + n;
    }
    sort(s + 1, s + 1 + n + n, cmp);
    // 找当前区间的最优后继
    for (int i = 1, j = 1; i <= n + n; i++) {
        while (j <= n + n && s[j].l <= s[i].r) j++;
        f[0][i] = j - 1;
    }
    // 倍增预处理
    for (int i = 1; i <= 16; i++) 
        for (int j = 1; j <= n + n; j++) 
            f[i][j] = f[i - 1][f[i - 1][j]];
    for (int i = 1; i <= n; i++) ans[s[i].id] = query(i);
    for (int i = 1; i <= n; i++) cout << ans[i] << ' ';
    cout << endl;
    return 0;
}

C++(clang++ 11.0.1) 解法, 执行用时: 284ms, 内存消耗: 75248K, 提交时间: 2023-07-07 21:03:24

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
typedef long long ll;
ll n,m,st[20][N<<1],anss[N];
struct node{
	ll l,r,id;
}a[N<<1];
bool cmp(node x,node y){
	return x.l<y.l;
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		ll l,r;
		cin>>l>>r;
		if(l>r){
			r+=m;
		}
		a[i].l=l;
		a[i].r=r;
		a[i].id=i;
	}
	sort(a+1,a+n+1,cmp);
	for(int i=1;i<=n;i++){
		a[i+n].l=a[i].l+m,a[i+n].r=a[i].r+m;
	}
	for(int i=1,j=1;i<=2*n;i++){
		while(j<=2*n&&a[j].l<=a[i].r){
			j++;
		}
		st[0][i]=j-1;
	}
	for(int i=1;i<=19;i++){
		for(int j=1;j<=2*n;j++){
			st[i][j]=st[i-1][st[i-1][j]];
		}
	}
	for(int i=1;i<=n;i++){
		ll up=a[i].l+m,ans=0,p=i;
		for(int j=19;j>=0;j--){
			if(st[j][p]&&a[st[j][p]].r<up){
				ans+=1<<j;
				p=st[j][p];
			}
		}
		anss[a[i].id]=ans+2;
	}
	for(int i=1;i<=n;i++){
		cout<<anss[i]<<" ";
	}
	return 0;
}