P9176 题解

lwwwb_555 · 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 指出，蟹蟹！