专栏文章

题解：P9447 [ICPC 2021 WF] Spider Walk

__awa_wangjiawen
P9447题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@min48bd0
此快照首次捕获于
2025/12/01 20:18
3 个月前
此快照最后确认于
2025/12/01 20:18
3 个月前
查看原文

一些定义

定义一座桥的距离为其到原点的距离。
定义两条丝线 x,yx,y 之间的距离为 min⁡(∣x−y∣,n−∣x−y∣)\min(|x-y|,n-|x-y|)。
定义 ansxans_x 为第 ii 条丝线到第 ss 条丝线最少要添加多少条桥。（也就是题目要求输出的答案）
本文中的所有第 ii 条丝线之类的中都对 nn 进行取模，为了方便不再说明。

分析

从头开始慢慢思考，先考虑特殊情况。
考虑一座桥也没有，很明显，此时第 ii 条丝线的答案就是其到第 ss 条线的距离。
还能注意到一个性质，相邻两条丝线的答案最多差 11。
证明也很简单，设 x,yx,y 两条丝线相邻，我们可以选择在这两条丝线之间加上一个距离极小的桥，这样就有 ansx=min⁡(ansx,ansy+1),ansy=min⁡(ansy,ansx+1)ans_x=\min(ans_x,ans_y+1),ans_y=\min(ans_y,ans_x+1)。因此 ansx,ansyans_x,ans_y 最多相差 11。
我们这里定义一对丝线 x,x+1x,x+1 是矛盾的为不满足 ansxans_x 与 ansx+1ans_{x+1} 差为 11。
距离远的桥不会对距离近的桥产生影响所以我们先把所有的桥按照距离从大到小排序，再依次加进网中并维护答案。
现在就是如何维护答案了，初始整张网为空，然后逐渐加入距离大的桥。初值我们已经确定了（不知道的话往上翻认真看），考虑维护答案。
一个桥连接的两条丝线都会经过，所以也就是交换了两侧的 ansans。
交换完后要注意依然需要保证所有丝线对是不矛盾的，这也是我们最主要要维护的。
当两个点 x,x+1x,x+1 交换后，只会有 x−1,xx-1,x 和 x+1,x+2x+1,x+2 这两对丝线可能出现矛盾。
我们可以对 x−1,x,x+1,x+2x-1,x,x+1,x+2 相邻两项的差进行分类讨论。
  1. ansx=ansx+1ans_x=ans_{x+1}
    这种情况交换没有意义，直接特判掉。
  2. ansx−1+3=ansx+2=ansx+1+1=ansx+2ans_{x-1}+3=ans_x+2=ans_{x+1}+1=ans_{x+2}
    这种情况交换完后还需要把 ansxans_x 减 11，并且还要对 x+2x+2 及后面的一些序列进行操作。
  3. ansx−1+2=ansx+1=ansx+1≥ansx+2ans_{x-1}+2=ans_x+1=ans_{x+1} \ge ans_{x+2}
    这种情况同第 22 种情况，但不需要对 x+2x+2 及后面的序列进行操作。
  4. ansx−1≥ansx&ansx+2=ansx+1+1=ansx+2ans_{x-1} \ge ans_x \& ans_x+2=ans_{x+1}+1=ans_{x+2}
    这种情况与第 33 种情况相反，不用把 ansxans_x 减 11，但是需要对 x+2x+2 及后面的序列进行操作。
  5. ansx−1+1=ansx+1=ansx+1=ansx+2ans_{x-1}+1=ans_x+1=ans_{x+1}=ans_{x+2}
    这是最简单的一种情况，只需要交换 ansxans_x 和 ansx+1ans_{x+1}，不用进行任何额外操作。
要注意，需要要判断是否把这个四元组反过来。（比如说 ansx+2+2=ansx+1+1=ansx≥ansx−1ans_{x+2}+2=ans_{x+1}+1=ans_x\ge ans_{x-1} 也算作第 22 种情况）
那我们该如何找需要对后面多长的序列进行操作呢？
考虑到要对一整个序列 [l,r][l,r] 进行操作，需要有 ∀i∈[l,r)ansi+1=ansi+1\forall i \in [l,r) ans_i+1=ans_{i+1}。故我们可以二分来找。
二分这个序列可能的最长的长度。我们可以查询 ansmidans_{mid}，若其到起始位置正好能构成一个公差为 11 的等差数列（设起始位置为 xx，即查询是否满足 ansi−ansx=i−xans_i-ans_x=i-x）。这个序列的单调性显然。证明如下。
设第一个不满足的点下标为 ii。因为保证了 ansans 数组相邻两项差最大为 11，故后面的数不可能补齐这个差，因此后面的数都不满足，因此有单调性。
区间减 11 我们可以用线段树维护，而交换相邻的两个数，因为它们最多差为 11，所以也可以进行分类讨论并进行单点修改。
一共要加进去 mm 条桥，二分的复杂度为 O(log⁡n)O(\log n)，线段树单次复杂度为 O(log⁡n)O(\log n)，总的复杂度为 O(mlog⁡2n)O(m\log ^2 n)。时限开到 6s，稍微卡卡常，然后相信洛谷神机吧。（大约跑了 2.8s）

代码

CPP
#include<bits/stdc++.h>
using namespace std;
const long long mod1=998244353;
const long long mod2=1000000007;
const long long inf=0x3f3f3f3f3f3f3f3f;
struct node{
	long long l,r,s;
	long long tagplus;
}Stree[4000101];
long long n,m,s;
pair<long long,long long>bird[500011];
long long a[200011];


void init();
void domemset();
long long read();
void write(long long x);

bool cmp(pair<long long,long long> x,pair<long long,long long> y)
{
	return x.first>y.first;
}

void pushdown(long long s)
{
	Stree[s<<1].s=Stree[s<<1].s+Stree[s].tagplus*(Stree[s<<1].r-Stree[s<<1].l+1);
	Stree[(s<<1)|1].s=Stree[(s<<1)|1].s+Stree[s].tagplus*(Stree[(s<<1)|1].r-Stree[(s<<1)|1].l+1);
	Stree[s<<1].tagplus+=Stree[s].tagplus;
	Stree[(s<<1)|1].tagplus+=Stree[s].tagplus;
	Stree[s].tagplus=0;
	return ;
}
void pushup(long long s)
{
	Stree[s].s=Stree[s<<1].s+Stree[(s<<1)|1].s;
	return ;
}
void build(long long l,long long r,long long s)
{
	Stree[s].l=l;Stree[s].r=r;
	if(l==r)
	{
		Stree[s].s=a[l];
//		cout<<l<<" "<<r<<" "<<s<<endl<<a[l]<<endl;
		return ;
	}
	long long mid=(l+r)>>1;
	build(l,mid,s<<1);build(mid+1,r,(s<<1)|1);
	pushup(s);
	return ;
}
void pplus(long long l,long long r,long long sum,long long s)
{
	if(Stree[s].l>r||Stree[s].r<l)
		return ;
	if(Stree[s].l>=l&&Stree[s].r<=r)
	{
		Stree[s].s=Stree[s].s+sum*(Stree[s].r-Stree[s].l+1);
		Stree[s].tagplus+=sum;
		return ;
	}
	pushdown(s);
	pplus(l,r,sum,s<<1);pplus(l,r,sum,(s<<1)|1);
	pushup(s);
	return ;
}
long long ffind(long long x,long long s)
{
	if(Stree[s].l>x||Stree[s].r<x)
		return 0;
	if(Stree[s].l==x&&Stree[s].r==x)
		return Stree[s].s;
	pushdown(s);
	return ffind(x,s<<1)+ffind(x,(s<<1)|1);
}

void doplus(long long l,long long r,long long sum,long long s)
{
	if(l<=r)
		pplus(l,r,sum,s);
	else
		pplus(l,n,sum,s),pplus(1,r,sum,s);
	return ;
}

long long findl(long long sum,long long x)
{
	long long l=1,r=n,mid,s;
	while(l<=r)
	{
		mid=(l+r)>>1;
		s=(x-mid+n+1)%n;
		if(s==0)
			s=n;
		if(ffind(s,1)==sum+mid-1)
			l=mid+1;
		else
			r=mid-1;
	}
	s=(x-r+n+1)%n;
	if(s==0)
		s=n;
	return s;
}
long long findr(long long sum,long long x)
{
	long long l=1,r=n,mid,s;
	while(l<=r)
	{
		mid=(l+r)>>1;
		s=(x+mid-1)%n;
		if(s==0)
			s=n;
		if(ffind(s,1)==sum+mid-1)
			l=mid+1;
		else
			r=mid-1;
	}
	s=(x+r-1)%n;
	if(s==0)
		s=n;
	return s;
}

void fun()
{
	domemset();
	n=read();m=read();s=read();
	for(int i=0;i<=n/2;i++)
		a[(s-i+n)%n]=a[(s+i)%n]=i;
	a[n]=a[0];
//	for(int i=1;i<=n;i++)
//		cout<<a[i]<<" ";
//	cout<<endl;
	build(1,n,1);
//	for(int j=1;j<=n;j++)
//		write(ffind(j,1)),putchar(' ');
//	putchar('\n');
	for(int i=1;i<=m;i++)
		bird[i].first=read(),bird[i].second=read();
	sort(bird+1,bird+m+1,cmp);
	for(int i=1;i<=m;i++)
	{
		long long x=bird[i].second;
		long long tmpx_=(x-2+n)%n+1,tmpx=x,tmpx1=x%n+1,tmpx2=(x+1)%n+1;
		tmpx=ffind(tmpx,1);tmpx1=ffind(tmpx1,1);
		if(tmpx==tmpx1)
			continue;
		tmpx_=ffind(tmpx_,1);tmpx2=ffind(tmpx2,1);
		if(tmpx_+1==tmpx&&tmpx+1==tmpx1)
		{
			if(tmpx1>=tmpx2)
			{
				doplus(x%n+1,x%n+1,-1,1);
//				continue;
			}
			else
			{
				long long tmpr=findr(tmpx1,x%n+1);
				doplus(x%n+1,tmpr,-1,1);
//				continue;
			}
		}
		else if(tmpx2+1==tmpx1&&tmpx1+1==tmpx)
		{
			if(tmpx>=tmpx_)
			{
				doplus(x,x,-1,1);
//				continue;
			}
			else
			{
				long long tmpl=findl(tmpx,x);
				doplus(tmpl,x,-1,1);
//				continue;
			}
		}
		else if(tmpx+1==tmpx1&&tmpx1+1==tmpx2)
		{
			long long tmpr=findr(tmpx2,(x+1)%n+1);
			doplus((x+1)%n+1,tmpr,-1,1);
			doplus(x,x,1,1);
			doplus(x%n+1,x%n+1,-1,1);
//			continue;
		}
		else if(tmpx+1==tmpx_&&tmpx1+1==tmpx)
		{
//			cout<<"qwq  ";
			long long tmpl=findl(tmpx_,(x-2+n)%n+1);
//			cout<<tmpl<<" "<<(x-2+n)%n+1<<endl;
			doplus(tmpl,(x-2+n)%n+1,-1,1);
			doplus(x,x,-1,1);
			doplus(x%n+1,x%n+1,1,1);
//			continue;
		}
		else if(tmpx==tmpx1+1)
		{
			doplus(x,x,-1,1);
			doplus(x%n+1,x%n+1,1,1);
//			continue;
		} 
		else
		{
			doplus(x,x,1,1);
			doplus(x%n+1,x%n+1,-1,1);
//			continue;
		}
//		cout<<tmpx_<<" "<<tmpx<<" "<<tmpx1<<" "<<tmpx2<<endl;
//		for(int i=1;i<=15;i++)
//			cout<<Stree[i].l<<" "<<Stree[i].r<<" "<<Stree[i].s<<" "<<Stree[i].tagplus<<endl;
//		cout<<endl;
//		for(int j=1980;j<=1983;j++)
//			write(ffind(j,1)),putchar(' ');
//		putchar('\n');putchar('\n');
//		for(int i=1;i<=15;i++)
//			cout<<Stree[i].l<<" "<<Stree[i].r<<" "<<Stree[i].s<<" "<<Stree[i].tagplus<<endl;
//		cout<<endl;
//		cout<<"QWQ\n\n";
	}
//	putchar('\n');
	for(int i=1;i<=n;i++)
		write(ffind(i,1)),putchar('\n');
	return ;
}
int main()
{
//	freopen("spider.in","r",stdin);
//	freopen("spider.out","w",stdout);
	srand(time(NULL));
	init();
//	t=read();
//	for(int i=1;i<=t;i++)
//	while(1)
		fun();
	return 0;
}


void init()
{

	return ;
}
void domemset()
{

	return ;
}
long long read()
{
	long long x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-')
			f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		x=(x<<3)+(x<<1)+(ch^'0');
		ch=getchar();
	}
	return x*f;
}
void write(long long x)
{
	if(x<0)
		putchar('-'),x=-x;
	if(x>=10)
		write(x/10);
	putchar((x%10)^'0');
	return ;
}

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...