BZOJ 4444: [Scoi2015]国旗计划

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <iostream>
#define MAXN 400010
using namespace std;
struct edge{
    int first;
    int next;
    int to;
}a[MAXN*2];
struct qvjian{
    int l,r,id;
    bool operator < (const qvjian &x)const{
        return l<x.l;
    }
}q[MAXN];
int dep[MAXN],s[MAXN],tail=0;
int n,m,ans[MAXN],num=0;
 
void addedge(int from,int to){
    a[++num].to=to;
    a[num].next=a[from].first;
    a[from].first=num;
}
 
void dfs(int now,int f,int head){
    dep[now]=dep[f]+1;s[++tail]=now;
    if(q[now].id!=0){
        while(head<tail&&q[s[head+1]].r>=q[now].l+m) head++;
        ans[q[now].id]=dep[now]-dep[s[head]]+1;
    }
    for(int i=a[now].first;i;i=a[i].next){
        int to=a[i].to;
        dfs(to,now,head);
    }
    tail--;
}
 
int main()
{   
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        int l,r;
        scanf("%d%d",&l,&r),q[i].id=i;
        if(l>r) r+=m;
        q[i].l=l,q[i].r=r;
        q[i+n].l=q[i].l+m,q[i+n].r=q[i].r+m,q[i+n].id=0;
    }
    int now=1;
    sort(q+1,q+2*n+1);
    for(int i=1;i<2*n;i++){
        while(now<2*n&&q[i].r>=q[now+1].l) now++;
        addedge(now,i);
    }
    dfs(2*n,0,1);
    for(int i=1;i<=n;i++) printf("%d ",ans[i]);
    return 0;
}