专栏文章

P9447 题解

KKSCD_
P9447题解参与者 5已保存评论 4

文章操作

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

当前评论
4 条
当前快照
1 份
快照标识符
@min460th
此快照首次捕获于
2025/12/01 20:16
3 个月前
此快照最后确认于
2025/12/01 20:16
3 个月前
查看原文
怎么题解区全是线段树，这个应该好写一些。

题意

nn 条射线绕中心形成一个环，有 mm 条连接相邻两射线的线段，两端点到中心距离相等。初始选择某射线向外走，遇到线段时强制走到另一端。可以任意加入满足同样限制的线段，对每个 ii 求初始在 ii 射线上走，最终走到 ss 射线无穷远处需要加入的最少线段数。n≤2×105,m≤5×105n\le 2\times 10^5,m\le 5\times 10^5。

题解

由于是强制走过线段，若按到中心的距离从大到小考虑，则每条线段相当于交换相邻两条射线的终点编号，要求即最终 ii 射线终点为 ss。考虑按该顺序 DP，设 fi,jf_{i,j} 表示考虑了前 ii 条给定线段，当前 jj 射线终点为 ss 的最小加入数，有初始值 f0,i=min⁡(∣s−i∣,n−∣s−i∣)f_{0,i}=\min(\left|s-i\right|,n-\left|s-i\right|)。
至于转移，先交换 fi−1,ti,fi−1,ti mod n+1f_{i-1,t_{i}},f_{i-1,t_{i}\bmod n+1}。之后还要考虑线段的加入，有 fi,j′=min⁡fi−1,k+min⁡(∣j−k∣,n−∣j−k∣)f'_{i,j}=\min f_{i-1,k}+\min(\left|j-k\right|,n-\left|j-k\right|)。由于只有两个位置变化，只需要尝试用较小值向外更新，并尝试更新较大值，可以做到单次 O(n)\mathcal O(n)，总复杂度 O(nm)\mathcal O(nm)，答案即 fm,if_{m,i}。
观察这个 DP 的形式，注意到差分数组只有 −1,0,1-1,0,1，否则一定可以更新，于是考虑维护差分数组 gi=fi−f(i+n−2) mod n+1g_i=f_{i}-f_{(i+n-2)\bmod n+1}。设 x=ti,y=ti mod n+1x=t_i,y=t_i\bmod n+1，gy=0g_y=0 时交换没有影响，以下以 gy=1g_y=1 为例，gy=−1g_y=-1 是类似的。
首先考虑 xx 位置的变化，fxf_x 先由于交换增加 11。此时若 gx=1g_x=1，则 fxf_x 还会被上个位置拉回来，于是 gxg_x 仍为 11，gyg_y 变成 00；否则就拉不回来了，gxg_x 增加 11，gyg_y 变成 −1-1。至于 yy 减小对其他位置的影响，显然无法更新前面元素，画图可得从 yy 向后找到首个非 11 位置 zz，此前的 ff 值均会减一，在 gg 上的影响即 gzg_z 增加 11。
这需要查询 yy 后面首个非 11 位置，在 gy=−1g_y=-1 时是前面首个非 −1-1 位置，用 set 分别维护两种下标，单点改的时候也修改 set 即可。另外若只考虑给定操作会将 ss 交换到 tt，则一定有 fm,t=0f_{m,t}=0，从该位置按 gg 数组推出 ff 即为答案，复杂度 O(mlog⁡n)\mathcal O(m\log n)。

代码

CPP
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+10;
int n,m,s,f[N],g[N]; pair<int,int> a[N];
set <int> sa,sb;
void cg(int p,int x)
{
	if(g[p]==1&&x!=1) sa.insert(p);
	if(g[p]!=1&&x==1) sa.erase(p);
	if(g[p]==-1&&x!=-1) sb.insert(p);
	if(g[p]!=-1&&x==-1) sb.erase(p);
	g[p]=x;
}
int main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>m>>s;
	for(int i=1;i<=m;i++) cin>>a[i].first>>a[i].second;
	for(int i=1;i<=n;i++) f[i]=min(abs(i-s),n-abs(i-s));
	sort(a+1,a+1+m);
	for(int i=1;i<=n;i++)
	{
		g[i]=f[i]-f[(i+n-2)%n+1];
		if(g[i]!=1) sa.insert(i);
		if(g[i]!=-1) sb.insert(i);
	}
	for(int _=m;_;_--)
	{
		int x=a[_].second,y=x%n+1;
		if(s==x||s==y) s=(s^x^y);
		if(!g[y]) continue;
		if(g[y]==1)
		{
			int z=-1; auto it=sa.upper_bound(y);
			if(it!=sa.end()) z=*it;
			else z=*sa.begin();
			cg(z,g[z]==0);
			if(g[x]==1) cg(y,0);
			else cg(y,-1),cg(x,g[x]==0);
		}
		else
		{
			int z=-1; auto it=sb.lower_bound(y);
			if(it!=sb.begin()) z=*prev(it,1);
			else z=*prev(sb.end(),1);
			cg(z,g[z]?0:-1),z=y%n+1;
			if(g[z]==-1) cg(y,0);
			else cg(y,1),cg(z,g[z]?0:-1);
		}
	}
	f[s]=0;
	for(int i=s;i>1;i--) f[i-1]=f[i]-g[i];
	for(int i=s+1;i<=n;i++) f[i]=f[i-1]+g[i];
	for(int i=1;i<=n;i++) cout<<f[i]<<'\n';
	return 0;
}

评论

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

正在加载评论...