P4155

发表于 更新于 分类于
[SCOI2015]国旗计划

[SCOI2015]国旗计划

和 P6902 差不多。

只不过这里需要开三倍的区间。

因为我们不只需要覆盖环，还需要看以每个区间为顶点的答案。

挺坑的。

时间复杂度 $O(n\log n)$。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
#include<iostream>
#include<cstdio>
#include<set>
#include<algorithm>
#define ll long long
using namespace std;

const ll N=6e5;

ll n,m,tot,l,r,ans;

ll f[N+5][30];

struct node{
	ll c,d,id,ans;
}a[N+5];

struct sett{
	ll v,id;
	bool operator < (const sett& rhs) const {
		return v<rhs.v;
	}
}t;

set<sett> s;

inline ll read() {
	ll ret=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9') {if(ch=='-') f=-f;ch=getchar();}
	while(ch>='0'&&ch<='9') {ret=(ret<<3)+(ret<<1)+ch-'0';ch=getchar();}
	return ret*f;
}

inline void write(ll x) {
	static char buf[22];static ll len=-1;
	if(x>=0) {
		do{buf[++len]=x%10+48;x/=10;}while(x);
	}
	else {
		putchar('-');
		do{buf[++len]=-(x%10)+48;x/=10;}while(x);
	}
	while(len>=0) putchar(buf[len--]);
}

bool cmp1(node x,node y) {
	return x.c<y.c;
}

bool cmp2(node x,node y) {
	return x.id<y.id;
}

int main() {

	n=read();m=read();

	for(ll i=1;i<=n;i++) {
		a[++tot].c=read();a[tot].d=read();
		a[tot].id=i;
		if(a[tot].d<a[tot].c) {
			a[tot].d+=m;
			tot++;
			a[tot].c=a[tot-1].c+m;
			a[tot].d=a[tot-1].d+m;
			a[tot].id=i;
		}
		else {
			tot++;
			a[tot].c=a[tot-1].c+m;
			a[tot].d=a[tot-1].d+m;
			a[tot].id=i;
			tot++;
			a[tot].c=a[tot-1].c+m;
			a[tot].d=a[tot-1].d+m;
			a[tot].id=i;
		}
	}

	sort(a+1,a+tot+1,cmp1);

	l=1;r=1;

	for(ll i=1;i<=tot;i++) {
		while(l<=tot&&a[l].c<a[i].c) {
			t.v=a[l].d;t.id=l;
			s.erase(t);l++;
		}
		while(r+1<=tot&&a[r+1].c<=a[i].d) {
			r++;t.v=a[r].d;t.id=r;
			s.insert(t);
		}
		f[i][0]=(*--s.end()).id;
	}

	for(ll j=1;j<=20;j++) {	
		for(ll i=1;i<=tot;i++) {
			f[i][j]=f[f[i][j-1]][j-1];
		}
	}

	for(ll i=1;i<=tot;i++) {
		if(a[i].d-a[i].c>=m) a[i].ans=1;
		ll x=i,tmp=1;
		for(ll k=20;k>=0;k--) {
			if(a[f[x][k]].d-a[i].c<m) {
				x=f[x][k];tmp+=1ll<<k;
			}
		}
		x=f[x][0];tmp+=1;a[i].ans=tmp;
	}

	sort(a+1,a+tot+1,cmp2);

	ans=N;
	for(ll i=1;i<=tot;i++) {
		ans=min(ans,a[i].ans);
		if(a[i].id==a[i+1].id) continue;
		write(ans);putchar(' ');
		ans=N;
	}
	
	return 0;
}