「SCOI2015」国旗计划 解题报告

「SCOI2015」国旗计划

蛮有趣的一个题

注意到区间互不交错，那么如果我们已经钦定了一个区间，它选择的下一个区间是唯一的，就是和它有交且右端点在最右边的，这个可以单调队列预处理一下

然后往后面跳拿倍增优化一下

---

Code:

#include <cstdio>

#include <cctype>

#include <algorithm>

#define int unsigned int

const int N=4e5+10;

template <class T>

void read(T &x)

{

	x=0;char c=getchar();

	while(!isdigit(c)) c=getchar();

	while(isdigit(c)) x=x*10+c-'0',c=getchar();

}

int n,m,ans[N],q[N],l,r,f[N][20];

struct yuucute

{

	int l,r,id;

	bool friend operator <(yuucute a,yuucute b){return a.r<b.r;}

}yuu[N];

signed main()

{

	read(n),read(m);

	for(int i=1;i<=n;i++)

	{

		read(yuu[i].l),read(yuu[i].r);

		if(yuu[i].r<yuu[i].l) yuu[i].r+=m;

		yuu[i].id=i;

		yuu[i+n]=yuu[i];

		yuu[i+n].l+=m,yuu[i+n].r+=m;

	}

	std::sort(yuu+1,yuu+1+(n<<1));

	f[n<<1][0]=n<<1,q[l=r=1]=n<<1;

	for(int i=(n<<1)-1;i;i--)

	{

		while(yuu[q[l]].l>yuu[i].r) ++l;

		f[i][0]=q[l];

		q[++r]=i;

	}

	for(int j=1;j<=19;j++)

		for(int i=1;i<=n<<1;i++)

			f[i][j]=f[f[i][j-1]][j-1];

	for(int i=1;i<=n;i++)

	{

		int x=i,l=yuu[i].l,id=yuu[i].id;

		for(int j=19;~j;j--)

			if(yuu[f[x][j]].r-l<m)

				x=f[x][j],ans[id]|=1<<j;

        ans[id]+=2;

	}

	for(int i=1;i<=n;i++) printf("%d ",ans[i]);

	return 0;

}

---

2019.3.3