90分 TLE求调

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

const int MAXN = 2e5 + 5;

struct node {
    int id, l, r;
    bool operator <(const node &b){
        return l < b.l;
    }
} a[2*MAXN];

int n, m, f[2*MAXN][64], ans[MAXN];

int main(){
    scanf("%d%d", &n, &m);
    for (register int i = 1; i <= n; i++){
        scanf("%d%d", &a[i].l, &a[i].r);
        if (a[i].r < a[i].l)
            a[i].r += m;
        a[i].id = i;
    }
    sort(a+1, a+n+1);
    for (register int i = 1; i <= n; i++){
        a[i+n] = a[i];
        a[i+n].l += m;
        a[i+n].r += m;
    }
    /*for (int i = 1; i <= 2 * n; i++){
        cout << a[i].id << " " << a[i].l << " " << a[i].r << endl;
    }*/
    for (register int i = 1; i <= 2 * n; i++){
        register int nxt = i; 
        for (register int j = i + 1; j <= 2 * n; j++){
            if (a[j].l > a[i].r) break;
            nxt = j;
        }
        f[i][0] = nxt;
        //cout << f[i][0] << " ";
    }
    //cout << endl;
    for (register int j = 1; (1 << j) <= 2 * n; j++){
        register int len = 1 << j;
        for (register int i = 1; i <= 2 * n - len; i++){
            f[i][j] = f[f[i][j-1]][j-1];
            //cout << f[i][j] << " ";
        }
        //cout << endl;
    }
    register int lgn = log2(n);
    for (register int i = 1; i <= n; i++){
        register int pos = i; 
        ans[a[i].id] = 1;
        for (register int j = lgn; j >= 0; j--){
            register int t = f[pos][j];
            if (a[t].l >= a[i].l + m || !t) continue;
            pos = t; ans[a[i].id] += (1 << j);
            if (a[pos].r >= a[i].l + m) break;
        }
    }
    for (register int i = 1; i <= n; i++){
        cout << ans[i] << " ";
    }
    cout << endl;
    return 0;
}