bzoj 4444 国旗计划

Posted on | Views:

$two\ pointer$ + 倍增.

首先破环成链,接一段长度为 $m$ 的在后面.因为区间不覆盖,对于一个区间 $(l,r)$ ,它后面应该接的区间可以贪心确定,就是左端点在 $[l,r]$ 范围内,而右端点最大的区间.这个可以通过 $two\ pointer$ 预处理.

然后用倍增的做法,处理 $f(i,j)$ 表示区间 $i$ 之后的第 $2^j$ 个区间标号.

查询时从 $i$ 开始跳,找到第一个区间使得区间总长 $\ge m$ 即可.时间复杂度 $O(n\cdot \log m)$ . 

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int MAXN=4e5+10;
struct node
{
	int l,r,id;
	node(int l=0,int r=0,int id=0):l(l),r(r),id(id) {}
	bool operator < (const node &rhs) const
	{
		return r<rhs.r;
	}
}p[MAXN];
int n,m,f[MAXN][20];
int ans[MAXN];
int main()
{
	n=read(),m=read();
	for(int i=1;i<=n;++i)
	{
		int l=read(),r=read();
		if(l>r)
			p[2*i-1]=node(l,r+m,i),p[2*i]=node(l+m,r+2*m,i);
		else
			p[2*i-1]=node(l,r,i),p[2*i]=node(l+m,r+m,i);
	}
	sort(p+1,p+1+2*n);
	for(int i=1,j=1;i<=2*n;++i)
	{
		while(j<2*n && p[j+1].l<=p[i].r)
			++j;
		f[i][0]=(i==j)?0:j;
	}
	for(int j=1;(1<<j)<=2*n;++j)
		for(int i=1;i<=2*n;++i)
			f[i][j]=f[f[i][j-1]][j-1];
	for(int i=1;i<=2*n;++i)
	{
		if(p[i].l>m)
			continue;
		int x=i,tmp=0;
		for(int j=19;j>=0;--j)
			if(f[x][j] && p[f[x][j]].r<p[i].l+m)
				x=f[x][j],tmp+=(1<<j);
		x=f[x][0];
		++tmp;
		ans[p[i].id]=tmp+(int)(p[i].id!=p[x].id);
	}
	for(int i=1;i<=n;++i)
		printf("%d ",ans[i]);
	puts("");
	return 0;
}