P4155 [SCOI2015]国旗计划

很有意思的一道题。

按套路破环成链，要注意右端点小于左端点的区间跨越了 (n o 1)。

假设钦定了某个士兵 (i)，接下来肯定贪心选择左端点小于等于当前右端点的右端点最大的下一个区间。因为区间不存在包含关系，所以形式化地讲就是找到最大的 (j) 使得 (C_jleq D_i)。

直接做是 (O(N^2)) 的，但观察到一条决策链中点的决策是存在重合的，即 (j) 的决策可以部分应用到 (i) 上面，并且存在单调性（因为不存在包含关系）。

考虑 (i) 和 (j) 之间连边，这样会形成一个决策森林。其中点 (u) 的答案为距离 (u) 最近的祖先 (v) 使得 (D_vgeq C_u+m)。

从根节点开始双指针，但上端点移动时需要朝着下端点的方向。这个只需要更新边表头就行了，即进入过的儿子直接跳过。

除排序外时间复杂度 (O(N))。

code:

#include<bits/stdc++.h>
using namespace std;
#define N 400005
#define For(i,x,y)for(i=x;i<=(y);i++)
#define Down(i,x,y)for(i=x;i>=(y);i--)
#define int long long
struct node
{
	int next,to;
}e[N];
struct soldier
{
	int c,d,id;
}a[N];
bool used[N];
int head[N],dep[N],res[200005],g,m;
inline void add(int u)
{
	e[++g].next=head[u];
	head[u]=g;
}
int read()
{
	int A;
	bool K;
	char C;
	C=A=K=0;
	while(C<'0'||C>'9')K|=C=='-',C=getchar();
	while(C>'/'&&C<':')A=(A<<3)+(A<<1)+(C^48),C=getchar();
	return(K?-A:A);
}
void write(int X)
{
	if(X<0)putchar('-'),X=-X;
	if(X>9)write(X/10);
	putchar(X%10|48);
}
inline bool cmp(soldier _,soldier __)
{
	return _.c<__.c;
}
void dfs(int l,int r)
{
	int i;
	while(head[r]&&a[head[r]].d>=a[l].c+m)r=head[r];
	/*cout<<l<<' '<<r<<' '<<head[r]<<' '<<a[l].c<<' '<<a[l].d<<' '<<a[r].c<<' '<<a[r].d<<endl;*/
	if(a[r].d>=a[l].c+m)res[a[l].id]=dep[l]-dep[r]+1;
	used[l]=1;
	for(i=head[l];i;i=e[i].next)
	{
		head[l]=i;
		dep[i]=dep[l]+1;
		dfs(i,r);
	}
}
signed main()
{
	int n,i,pos=1;
	n=read(),m=read();
	For(i,1,n)
	{
		a[i].c=read(),a[i].d=read();
		a[i].id=i;
		if(a[i].d<a[i].c)a[i].d+=m;
		a[i+n].c=a[i].c+m;
		a[i+n].d=a[i].d+m;
	}
	sort(a+1,a+(n<<1|1),cmp);
	For(i,1,n<<1)
	{
		while(pos<n<<1&&a[pos+1].c<=a[i].d)pos++;
		if(pos!=i)add(pos);
		/*cout<<pos<<' '<<i<<' '<<head[pos]<<endl;*/
	}
	Down(i,n<<1,1)
	if(!used[i])dfs(i,i);
	For(i,1,n)write(res[i]),putchar(' ');
	return 0;
}