求纠错

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<queue>
using namespace std;
const int N=4e5+10;
struct qj{
	int l,r;int id;
	inline bool operator <(qj b)const{
		return r<b.r;
	}
}a[N<<1];
int to[31][N<<1];
int st[N<<2];int top=0;
int tr[N<<1];
#define lowbit(a) ((a)&(-a))
inline int Query(int p){
	register int k=0;
	while(p) {if(a[tr[p]].r>a[k].r||(!k)) k=tr[p];p-=lowbit(p);}
	return k;
}
inline int Get(int x){return (lower_bound(st+1,st+1+top,x)-st);}
inline void update(int p,int k)
{
	while(p<=top) {if((!tr[p])||a[tr[p]].r<a[k].r) tr[p]=k;p+=lowbit(p);}
	return;
}
int ans[N];
int main()
{
	int n,m;scanf("%d%d",&n,&m);top=0;
	for(register int i=1;i<=n;++i) {
		scanf("%d%d",&a[i].l,&a[i].r);a[i].id=i;
		if(a[i].l>=a[i].r) a[i].r+=m;
		st[++top]=a[i].l,st[++top]=a[i].r;
	}
	register int nn=n;
	for(register int i=1;i<=nn;++i){
		if(a[i].l<=m&&a[i].r<=m) {
			a[++n]=(qj){a[i].l+m,a[i].r+m};
			st[++top]=a[n].l,st[++top]=a[n].r;
		}
	}
	sort(st+1,st+1+top);
	top=unique(st+1,st+1+top)-st-1;
	sort(a+1,a+1+n);
	for(register int i=n;i;--i){
		to[0][i]=Query(Get(a[i].r));
		update(Get(a[i].l),i);
	}
	for(register int i=1;i<=30;++i)
		for(register int j=1;j<=n;++j)
			to[i][j]=to[i-1][to[i-1][j]];
	for(register int i=1;i<=n;++i){
		if(a[i].id!=0){
			register int R=a[i].l+m;register int u=i,id=a[i].id;
			for(register int j=30;~j;--j) if(to[j][u]!=0&&a[to[j][u]].r<R) u=to[j][u],ans[id]+=(1<<j);
			ans[id]+=2;
		}
	}
	for(register int i=1;i<=nn;++i) {if(ans[i+1]==260)ans[i]-=1;printf("%d ",ans[i]);}
	puts("");
}