本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-11-20 16:38:20

怎么题解区全是线段树，这个应该好写一些。

题意

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

题解

由于是强制走过线段，若按到中心的距离从大到小考虑，则每条线段相当于交换相邻两条射线的终点编号，要求即最终 $i$ 射线终点为 $s$。考虑按该顺序 DP，设 $f_{i,j}$ 表示考虑了前 $i$ 条给定线段，当前 $j$ 射线终点为 $s$ 的最小加入数，有初始值 $f_{0,i}=\min(\left|s-i\right|,n-\left|s-i\right|)$。

至于转移，先交换 $f_{i-1,t_{i}},f_{i-1,t_{i}\bmod n+1}$。之后还要考虑线段的加入，有 $f'{i,j}=\min f{i-1,k}+\min(\left|j-k\right|,n-\left|j-k\right|)$。由于只有两个位置变化，只需要尝试用较小值向外更新，并尝试更新较大值，可以做到单次 $\mathcal O(n)$，总复杂度 $\mathcal O(nm)$，答案即 $f_{m,i}$。

观察这个 DP 的形式，注意到差分数组只有 $-1,0,1$，否则一定可以更新，于是考虑维护差分数组 $g_i=f_{i}-f_{(i+n-2)\bmod n+1}$。设 $x=t_i,y=t_i\bmod n+1$，$g_y=0$ 时交换没有影响，以下以 $g_y=1$ 为例，$g_y=-1$ 是类似的。

首先考虑 $x$ 位置的变化，$f_x$ 先由于交换增加 $1$。此时若 $g_x=1$，则 $f_x$ 还会被上个位置拉回来，于是 $g_x$ 仍为 $1$，$g_y$ 变成 $0$；否则就拉不回来了，$g_x$ 增加 $1$，$g_y$ 变成 $-1$。至于 $y$ 减小对其他位置的影响，显然无法更新前面元素，画图可得从 $y$ 向后找到首个非 $1$ 位置 $z$，此前的 $f$ 值均会减一，在 $g$ 上的影响即 $g_z$ 增加 $1$。

这需要查询 $y$ 后面首个非 $1$ 位置，在 $g_y=-1$ 时是前面首个非 $-1$ 位置，用 set 分别维护两种下标，单点改的时候也修改 set 即可。另外若只考虑给定操作会将 $s$ 交换到 $t$，则一定有 $f_{m,t}=0$，从该位置按 $g$ 数组推出 $f$ 即为答案，复杂度 $\mathcal O(m\log n)$。

代码

#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;
}