[SCOI2015]国旗计划

[SCOI2015]国旗计划

注意一个关键点，没有一个区间是包含在另一个区间的，这意味着区间之间要么相交要么相离，
当有一个区间一定加入时，我们可以二分查找去得到下一个区间的，但是这样速度显然太慢了，所以我们利用倍增来优化。

定义表示号节点为左端点，共有条线段连在一起最有可到达的坐标。
然后只需要从小到大初始化数组，从大到小枚举选择就行了。

/*
  Author : lifehappy
*/
#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 10;

int n, m, tot, cnt, b[N], id[N][25];

struct segment {
    int l, r;

    segment(int _l = 0, int _r = 0) : l(_l), r(_r) {}

    bool operator < (const segment &t) const {
        return l < t.l;
    }
}a[N], la[N];

inline int ID(int x) {
    return lower_bound(b + 1, b + 1 + cnt, x) - b;
}

int main() {
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    // ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    scanf("%d %d", &n, &m);
    for(int i = 1; i <= n; i++) {
        int l, r;
        scanf("%d %d", &l, &r);
        a[i] = segment(l, r);
        if(r < l) la[++tot] = segment(l, r + m), la[++tot] = segment(l + m, 2 * m);
        else la[++tot] = segment(l, r), la[++tot] = segment(l + m, r + m);
    }
    for(int i = 1; i <= tot; i++) {
        b[++cnt] = la[i].l;
        b[++cnt] = la[i].r;
    }
    sort(b + 1, b + 1 + cnt), sort(la + 1, la + tot + 1);
    cnt = unique(b + 1, b + 1 + cnt) - (b + 1);
    int pos = 1, maxr = 0;
    for(int i = 1; i <= cnt; i++) {
        while(pos <= tot && la[pos].l <= b[i]) {
            maxr = max(maxr, la[pos].r);
            pos++;
        }
        id[i][0] = ID(maxr);//我们一定是找一个最大右端点，这样才是最优的。
    }
    for(int k = 1; k <= 20; k++) {
        for(int i = 1; i <= cnt; i++) {
            id[i][k] = id[id[i][k - 1]][k - 1];
        }
    }
    for(int i = 1; i <= n; i++) {
        int l = a[i].l, r = a[i].r, target, res = 1;
        if(l > r) r += m;
        r = ID(r), target = l + m;
        for(int k = 20; k >= 0; k--) {
            if(b[id[r][k]] < target) {
                res += (1 << k);
                r = id[r][k];
            }
        }
        res++;
        printf("%d%c", res, i == n ? '\n' : ' ');
    }
    return 0;
}