题解 [ABC338D] Island Tour
cjh20090318
·
·
题解
被降智的一道简单题。
题意
有一条长度为 $M$ 的旅游序列 $X$，你需要按照顺序依次经过这些点，选择断掉一座桥使得旅游经过的桥最少。
## 分析
设断掉第 $i$ 座桥会因为绕行增加旅行长度的值为 $s_i$。
从 $p$ 点到 $q$ 点的最短距离是 $\min(\vert p-q \vert , n - \vert p - q \vert )$，那么分类讨论。
不妨设 $p<q$。
设多绕行的距离为 $d = \left\vert n - 2(q - p) \right\vert$。
分类讨论三种情况。
### 当 $q-p < n-(q-p)$ 时
如果断掉了 $p \sim q-1$ 之间任意一座桥，总的旅程就会增加 $d$，所以 $\forall i \in [p,q), s_i \gets s_i+d$。
### 当 $q-p > n-(q-p)$ 时
如果断掉了 $1 \sim p-1$ 或 $q \sim n$ 之间任意一座桥，总的旅程就会增加 $d$，所以 $\forall i \in [1,p) \cup [q,n], s_i \gets s_i+d$。
### 当 $q-p = n-(q-p)$ 时
无论怎么走路程都是一样的，所以不处理。
然后这就是一个区间修改单点查询的问题，~~可以使用线段树~~，但是因为只在最后查询，所以可以使用差分。
线段树修改查询为 $O(n \log n)$，差分修改查询为 $O(n)$。
## 代码
### ~~赛时的~~线段树做法
```cpp
//the code is from chenjh
#include<iostream>
#include<cstdio>
#include<algorithm>
#define MAXN 200002
using namespace std;
typedef long long LL;
int n,m;
int x[MAXN];
LL mn[MAXN<<2],lazy[MAXN<<2];//线段树区间修改维护最小值。
#define lson (rt<<1)
#define rson (rt<<1|1)
using ci=const int;
void pd(ci rt,ci l,ci r){
mn[lson]+=lazy[rt],lazy[lson]+=lazy[rt];
mn[rson]+=lazy[rt],lazy[rson]+=lazy[rt];
lazy[rt]=0;
}
void update(ci rt,ci l,ci r,ci L,ci R,ci val){
if(L<=l && r<=R){mn[rt]+=val,lazy[rt]+=val;return;}
pd(rt,l,r);
int mid=(l+r)>>1;
if(L<=mid) update(lson,l,mid,L,R,val);
if(mid<R) update(rson,mid+1,r,L,R,val);
mn[rt]=min(mn[lson],mn[rson]);
}
LL query(ci rt,ci l,ci r,ci L,ci R){
if(L<=l && r<=R) return mn[rt];
pd(rt,l,r);
int mid=(l+r)>>1;
LL ret=0x3f3f3f3f3f3f3f3fll;
if(L<=mid) ret=min(ret,query(lson,l,mid,L,R));
if(mid<R) ret=min(ret,query(rson,mid+1,r,L,R));
return ret;
}
int main(){
cin>>n>>m;
LL ans=0;
for(int i=1;i<=m;i++) cin>>x[i];
for(int i=2;i<=m;i++) ans+=min(abs(x[i]-x[i-1]),n-abs(x[i]-x[i-1]));//不断桥的最小距离。
for(int i=2;i<=m;i++){
int p=x[i-1],q=x[i];
if(p>q) swap(p,q);
if(((q-p)<<1)<n) update(1,1,n,p,q-1,n-((q-p)<<1));
else if(((q-p)<<1)>n){
if(p>1) update(1,1,n,1,p-1,((q-p)<<1)-n);
update(1,1,n,q,n,((q-p)<<1)-n);
}//线段树修改。
}
LL mn=0x3f3f3f3f3f3f3f3fll;
for(int i=1;i<=n;i++) mn=min(mn,query(1,1,n,i,i));//线段树单点查询。
printf("%lld\n",ans+mn);
return 0;
}
```
### ~~复杂度更优秀的~~差分做法
```cpp
//the code is from chenjh
#include<cstdio>
#include<algorithm>
#define MAXN 200002
using namespace std;
typedef long long LL;
int n,m;
int x[MAXN];
LL s[MAXN];
int main(){
scanf("%d%d",&n,&m);
LL ans=0;
for(int i=1;i<=m;i++) scanf("%d",&x[i]);
for(int i=2;i<=m;i++){
int p=x[i-1],q=x[i];
if(p>q) swap(p,q);
ans+=min(q-p,n-q+p);//不断桥的最小距离。
if(((q-p)<<1)<n) s[p]+=n-((q-p)<<1),s[q]-=n-((q-p)<<1);
else if(((q-p)<<1)>n){
s[1]+=((q-p)<<1)-n,s[p]-=((q-p)<<1)-n;
s[q]+=((q-p)<<1)-n;
}//差分修改。
}
LL mn=0x3f3f3f3f3f3f3f3fll;
for(int i=1;i<=n;i++) mn=min(mn,s[i]+=s[i-1]);//差分还原的同时取增加的最小值。
printf("%lld\n",ans+mn);
return 0;
}
```