专栏文章

题解：AT_abc430_d [ABC430D] Neighbor Distance

qqdl66666666
AT_abc430_d题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@min8qmjp
此快照首次捕获于
2025/12/01 22:24
3 个月前
此快照最后确认于
2025/12/01 22:24
3 个月前
查看原文

权值线段树写法

题意

有一条数轴，初始时只有编号为 00 的人站在坐标 00 处。
接着，编号为 1,2,…,N1, 2, …, N 的人依次到达，并站在数轴上。第 ii 个人站在坐标 Xi（Xi≥1X_i （ X_i \ge 1 ，且所有 XiX_i 互不相同）。
每当一个人到达后，需要回答以下问题：
假设当前数轴上有 r+1r+1 个人（编号 0∼r0\sim r），定义每个人 ii 的 did_i 为该人到最近另一个人的距离（即 di=min⁡j≠iXi−Xjd_i = \min_{j \neq i} X_i - X_j ）。
要求计算当前所有 r+1r+1 个人的 did_i 的总和，即 ∑i=0rdi\sum_{i=0}^{r} d_i 。

分析

我们在全局开一个 ansans，记录当前答案。
考虑加入一个人会造成什么影响？ 注意到新加入一个人 pp 只会影响到当前他左边第一个人 ll 和右边第一个人 rr。
我们设 pp 到 ll 的距离为 disldisl，pp 到 rr 的距离为 disrdisr。
显然 dis[p]dis[p] 就等于 min⁡(disl,disr)\min(disl,disr)，如果 disl disl 小于 dis[l]dis[l] 就更新；同样的，若 disrdisr 小于 dis[r]dis[r]，相应的它们的贡献也会从 ansans 中加或删去。
所以问题转化为
  • 找到一个点左边的第一个点和它的坐标，右边的第一个的和它的坐标。
  • 加入这个点。

权值线段树

顾名思义，把权值看作下标，这里我们需要一些小技巧来完成这个题。
CPP
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]; 
	}
我们将坐标看作线段树中的区间下标。
将坐标离散化，pp 是坐标对应的离散值，pos[i]pos[i] 记录 pp，用于顺序插入坐标；val[p]val[p] 表示 pp 所对应的原坐标值，用于计算距离。
查询 pp 的左边第一个数，等价于在 [0,p][0,p] 中查询最大的出现过的值；查询右边第一个则等价于在 [p,n][p,n] 中查询最小的出现过的值。用权值树维护区间 maxn,minnmaxn,minn，每单点插入更新一下最值即可。
时间复杂度 O(nlog⁡n)O(n\log n)，可以通过。
细节自己要好好处理一下。
CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...