P9447 题解
KSCD_
·
·
题解
怎么题解区全是线段树，这个应该好写一些。
题意
### 题解
由于是强制走过线段，若按到中心的距离从大到小考虑，则每条线段相当于交换相邻两条射线的终点编号，要求即最终 $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)$。
### 代码
~~~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;
}
~~~