自动搬运

查看原文

来自洛谷，原作者为

	lwwwb_555 Dreams come true

搬运于2025-08-24 22:46:03，当前版本为作者最后更新于2023-10-23 20:33:16，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目传送门：P9176

看到 dalao 们都写的平衡树或树状数组，此蒟蒻在这里写一篇线段树的。

Solution

先将所有人的身高离线下来，构建权值线段树，用线段树记录身高在 $l$ 到 $r$ 内的总人数，对于每一个信息，先将线段树上每一个包括了 $v_i$ 的区间的权值加上 $a_i$，然后再进行查询。

我们可以用 $sum$ 记录从第一条信息到第 $i$ 条信息的总人数，当 $sum \bmod 2=1$ 时查找第 $sum/2+1$ 个人的身高，否则就要找中间的身高较矮的那个人即 $sum/2$ 的身高。

其他的细节详见代码注释。

Code

#include<bits/stdc++.h>
using namespace std;
int n,btot,ctot;
long long c[200005],bb[200005];
struct node{
	long long v;
	long long a;
}t[200005];
struct nn{
	int ll,rr;
	long long w;
}tt[800005];
void b(int p,int l,int r){
	tt[p].ll=l;
	tt[p].rr=r;
	tt[p].w=0ll;
	if(l==r){
		return;
	}
	int mid=(l+r)>>1;
	b(p*2,l,mid);
	b(p*2+1,mid+1,r);
}
void add(int p,int l,long long k){
	if(tt[p].ll==tt[p].rr){
		tt[p].w+=k;
		return;
	}
	int mid=(tt[p].ll+tt[p].rr)>>1;
	if(l<=mid){
		add(p*2,l,k);
	}else{
		add(p*2+1,l,k);
	}
	tt[p].w=tt[p*2].w+tt[p*2+1].w;
}
int ans=0;
void query(int p,long long l){
	if(tt[p].ll==tt[p].rr){
		ans=tt[p].ll;//已经搜索到叶子节点了,此时将ans更新为离散化后的身高
		return;
	}
	if(l<=tt[p*2].w){//先判断第l个数是否在左区间里,如果在,就直接进入左区间查找,否则就计算第l个数为右区间的第几个,再进入右区间查找
		query(p*2,l);
	}else{
		query(p*2+1,l-tt[p*2].w);
	}
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%lld%lld",&t[i].v,&t[i].a);
		bb[++btot]=t[i].v;
	}
	sort(bb+1,bb+btot+1);
	for(int i=1;i<=btot;i++){
		if(i==1 || bb[i]!=bb[i-1]){
			c[++ctot]=bb[i];//离散化
		}
	}
	b(1,1,ctot);//建树
	long long sum=0;
	for(int i=1;i<=n;i++){
		int p=lower_bound(c+1,c+ctot+1,t[i].v)-c;//身高在离散化后的值就为p
		add(1,p,t[i].a);
		sum+=t[i].a;
		ans=0;
		if(sum%2ll==1ll){
			query(1,sum/2ll+1ll);
		}else{
			query(1,sum/2ll);
		}
		printf("%lld\n",c[ans]);
	}
	return 0;
}
//不开long long见祖宗

蒟蒻的第一篇题解，如有描述得不清楚的地方欢迎各位 dalao 指出，蟹蟹！