Question

有 \(n\) 座海岛由 \(n\) 条桥连着，第 \(i\) 座桥连接第 \(i\) 和 \(i+1\) 座海岛，第 \(n\) 座桥连接第 \(n\) 和 \(1\) 座海盗

有一条长度为 \(m\) 的旅游路线，第 \(X_i\) 表示依次到达的岛屿

现在需要切断一条桥，求总旅游路线最小值

Solution

显然，从第 \(X_{i-1}\) 到 \(X_i\) 有两条路可以走，一条路是 \(|X_i-X_{i-1}|\) 另外一条路是 \(n-|X_i-X_{i-1}|\)

我们肯定选择短的那一条，不妨设短的那条路径长度为 \(x\)

如果短的那一条其中有一条道路被封死了，那么只能绕路，增加的路程就是 \((n-x)-x=n-2x\)

对于短的道路上的每一条路，我们把这个增量加到这条路的每一座桥上面

对于每个 \(X_{i-1},X_i\) 都重复这个过程

总增量最小的那座桥就是被切断的桥

区间加+单点查询可以用树状数组或者线段树实现

Code

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int INF = 1LL<<60;
const int maxn = 4e5 + 10;
int n,m;
int q[maxn],c[maxn];
int read(){
    int ret=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch)){ret=ret*10+ch-'0';ch=getchar();}
    return ret*f;
}

int get(int x){
    int ret = 0 ;
        for(;x;x-=x&-x) ret += c[x];
    return ret;
}
void add(int x,int d){
    for(;x<maxn;x+=x&-x) c[x] += d;
}

signed main(){
    freopen("D.in","r",stdin);
    n=read();m=read();
    int ans = 0;
    for(int i=1;i<=m;i++) q[i]=read();
    for(int i=2;i<=m;i++){
        if(abs(q[i]-q[i-1]) < n - abs(q[i]-q[i-1])){
            int x = abs(q[i]-q[i-1]);
            ans += x;
            int d = n - 2*x;
            int L = min(q[i],q[i-1]), R = max(q[i],q[i-1]);
            add(L,d); add(R,-d);
        }
        else{
            int x = n - abs(q[i]-q[i-1]);
            ans += x;
            int d = n- 2*x;
            int L = min(q[i],q[i-1]), R = max(q[i],q[i-1]);
            add(1,d); add(L,-d); add(R,d); add(n+1,-d);
        }
    }
    int add_ans = INF;
    for(int i=1;i<=n;i++){
        add_ans = min(add_ans, get(i));
    }
    cout<<ans + add_ans<<endl;
    return 0;
}