기준 (JUNGOL 9657)

https://jungol.co.kr/problem/9657

---

아이디어

미리 모든 쿼리들을 입력받아서 가능한 키 값들을 값 압축을 해주어서 1부터 20만까지의 수로 변환해줍시다. 그리고 다시 쿼리들을 앞에서부터 보면서 키가 a인 학생이 x명 들어오면 arr[a]에 x를 더하는 것을 반복해주면 됩니다. 이를 세그먼트 트리에 넣어주면 여기서 임의의 k에 대해 k번째로 작은 학생의 키를 O(log 200000)에 알아낼 수 있습니다. 그러므로 쿼리들을 진행해가면서 그때까지의 총 학생수를 sum이라고 하고, sum이 짝수라면 sum/2번째와 sum/2+1번째 학생중 더 작은 키를, sum이 홀수라면 (sum+1)/2번째 학생의 키를 출력해주면 됩니다.

---

소스코드

#include <iostream>
#include <vector>
#include <algorithm>
#define ll long long
using namespace std;

ll tree[808080]={0};
void update(ll s,ll e,ll node,ll idx,ll num)
{
    if (idx<s || e<idx) return;
    tree[node]+=num;
    if (s==e) return;
    ll mid=(s+e)/2;
    update(s,mid,node*2,idx,num);
    update(mid+1,e,node*2+1,idx,num);
}
ll Find(ll s,ll e,ll node,ll num)
{
    if (s==e) return s;
    ll mid=(s+e)/2;
    if (tree[node*2]>=num) return Find(s,mid,node*2,num);
    else return Find(mid+1,e,node*2+1,num-tree[node*2]);
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    ll N,i,a,b;
    vector <ll> nums;
    vector <pair <ll,ll> > query;

    cin>>N;
    for (i=0;i<N;i++)
    {
        cin>>a>>b;
        nums.push_back(a);
        query.push_back({a,b});
    }

    sort (nums.begin(),nums.end());
    nums.erase(unique(nums.begin(),nums.end()),nums.end());

    ll sum=0;
    for (i=0;i<N;i++)
    {
        ll idx=lower_bound(nums.begin(),nums.end(),query[i].first)-nums.begin()+1;
        update(1,N,1,idx,query[i].second);
        sum+=query[i].second;

        if (sum%2==0) cout<<nums[min(Find(1,N,1,sum/2),Find(1,N,1,sum/2+1))-1]<<"\n";
        else cout<<nums[Find(1,N,1,sum/2+1)-1]<<"\n";
    }
}