题解：AT_abc430_d [ABC430D] Neighbor Distance

qdl66666666 · 2025-11-13 21:14:53 · 题解

权值线段树写法

题意

有一条数轴，初始时只有编号为 0 的人站在坐标 0 处。
接着，编号为 1, 2, …, N 的人依次到达，并站在数轴上。第 i 个人站在坐标 X_i （ X_i \ge 1 ，且所有 X_i 互不相同）。

每当一个人到达后，需要回答以下问题：
假设当前数轴上有 r+1 个人（编号 0\sim r），定义每个人 i 的 d_i 为该人到最近另一个人的距离（即 d_i = \min_{j \neq i} X_i - X_j ）。
要求计算当前所有 r+1 个人的 d_i 的总和，即 \sum_{i=0}^{r} d_i 。

分析

我们在全局开一个 ans，记录当前答案。

考虑加入一个人会造成什么影响？ 注意到新加入一个人 p 只会影响到当前他左边第一个人 l 和右边第一个人 r。

我们设 p 到 l 的距离为 disl，p 到 r 的距离为 disr。

显然 dis[p] 就等于 \min(disl,disr)，如果 disl 小于 dis[l] 就更新；同样的，若 disr 小于 dis[r]，相应的它们的贡献也会从 ans 中加或删去。

所以问题转化为

• 找到一个点左边的第一个点和它的坐标，右边的第一个的和它的坐标。
• 加入这个点。

  权值线段树

  顾名思义，把权值看作下标，这里我们需要一些小技巧来完成这个题。

  for(int i=1;i<=n;i++){
      int p = lower_bound(b+1,b+n+1,x[i]) - b;
      pos[i] = p; val[p] = x[i]; 
  }

  我们将坐标看作线段树中的区间下标。
  将坐标离散化，p 是坐标对应的离散值，pos[i] 记录 p，用于顺序插入坐标；val[p] 表示 p 所对应的原坐标值，用于计算距离。

查询 p 的左边第一个数，等价于在 [0,p] 中查询最大的出现过的值；查询右边第一个则等价于在 [p,n] 中查询最小的出现过的值。用权值树维护区间 maxn,minn，每单点插入更新一下最值即可。

时间复杂度 O(n\log n)，可以通过。

细节自己要好好处理一下。

#include<bits/stdc++.h>
#define ll long long
#define mid ((l+r)>>1)
#define ls rt<<1
#define rs rt<<1|1
#define lson ls,l,mid
#define rson rs,mid+1,r
#define fi first
#define se second
using namespace std;
const int N = 1e6 + 10;
template<typename TY>
inline void read(TY &s){
    ll x = 0,f = 1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    s = x * f;
}
void _write(ll x){
    if(x < 0) putchar('-'),x=-x;
    if(x > 9) _write(x/10);
    putchar(x%10+'0');
}
inline void write(ll x,char ch){
    _write(x); cout << ch;
}
int n,x[N],b[N]; 
ll dis[N],ans;
ll val[N],pos[N];
int minn[N<<2],maxn[N<<2];
void update(int rt,int l,int r,int v){
    minn[rt] = min(minn[rt],v); maxn[rt] = max(maxn[rt],v);
    if(l == r) return;
    if(v <= mid) update(lson,v);
    else update(rson,v);
}
int query_r(int rt,int l,int r,int ql,int qr){
    if(ql <= l && r <= qr) return maxn[rt];
    int res = -1;
    if(ql <= mid) res = max(res,query_r(lson,ql,qr));
    if(mid + 1 <= qr) res = max(res,query_r(rson,ql,qr));
    return res;
}
int query_l(int rt,int l,int r,int ql,int qr){
    if(ql <= l && r <= qr) return minn[rt];
    int res = 0x3f3f3f3f;
    if(ql <= mid) res = min(res,query_l(lson,ql,qr));
    if(mid + 1 <= qr) res = min(res,query_l(rson,ql,qr));
    return res;
}
int main(){
    read(n);
    for(int i=1;i<=n;i++){
        read(x[i]);
        b[i] = x[i];
    }
    sort(b+1,b+n+1);
    for(int i=0;i<=n;i++) dis[i] = 1e18;
    for(int i=1;i<=n;i++){
        int p = lower_bound(b+1,b+n+1,x[i]) - b;
        pos[i] = p; val[p] = x[i]; 
    }
    memset(minn,0x3f,sizeof minn);
    memset(maxn,-1,sizeof maxn);
    update(1,0,n,0);
    ans = 1e18;
    for(int i=1;i<=n;i++){
        int p = pos[i];
        int l = query_r(1,0,n,0,p),r = query_l(1,0,n,p,n);//找出最小的 l 和 最大的 r 
        if(l != -1){
//          cerr << p << "->";
            ll disl = val[p]-val[l];
//          cerr << dis[p] << "disl->";
            dis[p] = min(dis[p],disl);
            if(dis[l] > disl){
                ans -= dis[l];
                dis[l] = disl;
                ans += dis[l];
            }
//          cerr << ans << "ans_l\n";
        }
        if(r != 0x3f3f3f3f){
//          cerr << r << "r\n";
            ll disr = val[r]-val[p];
            dis[p] = min(dis[p],disr);
            if(dis[r] > disr){
                ans -= dis[r];
                dis[r] = disr;
                ans += dis[r];
            }
        }
        update(1,0,n,p);//单点更新 p  
        ans += dis[p];
//      cerr << dis[p] << "dis[p]\n";
        cout << ans << "\n"; 
    }
    return 0;
}