线段树是什么东西？论码量还得是树状数组啊！

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+10;
struct node{int x,y;}e[N];map<int,int>mp;int b[N];
int c[N],len;
void add(int x,int k){for(;x<=len;x+=x&-x)c[x]+=k;}
int get(int x){int ans=0;for(;x;x-=x&-x)ans+=c[x];return ans;}
signed main()
{
	int n;cin>>n;
	for(int i=1;i<=n;i++)cin>>e[i].x>>e[i].y,b[i]=e[i].x;
	sort(b+1,b+n+1);len=unique(b+1,b+n+1)-b-1;
	for(int i=1;i<=len;i++)mp[b[i]]=i;
	int sum=0;
	for(int i=1;i<=n;i++)
	{
		add(mp[e[i].x],e[i].y),sum+=e[i].y;
		int l=0,r=len,ans=0;
		while(l<=r)
		{
			int mid=(l+r)>>1;
			if(get(mid)<(sum+1)/2)l=mid+1,ans=mid;
			else r=mid-1;
		}
		cout<<b[ans+1]<<'\n';
	}
	return 0;
}

题目传送门：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 指出，蟹蟹！