SMMR-246: Median (Segment Tree)

#include <bits/stdc++.h>

using namespace std;
const int INF = 1e9;
const int N = 2e5;
int tree[1 << 19];
int pst[N+10], ar[N+10];
unordered_map <int, int> num; // num[number] -> position
int n;

void update(int idx, int l, int r, int upd){
    if(l == r) {
        tree[idx] = 1;
        return;
    }
    int mid = (l + r) / 2;
    if(upd <= mid) update(2*idx, l, mid, upd);
    else update(2*idx+1, mid+1, r, upd);
    tree[idx] = tree[2*idx] + tree[2*idx+1];
}

void update_tree(int x){
    update(1, 1, n, num[x]);
    num[x] ++;
}

int query1(int x){
    int l = 1, r = n, idx = 1;
    while(l != r){
        int mid = (l + r) / 2;
        if(x > tree[2*idx]){
            x -= tree[2*idx];
            idx = 2 * idx + 1;
            l = mid + 1;
        }
        else {
            idx = 2 * idx;
            r = mid;
        }
    }
    return r;
}

int query2(int x){
    int l = 1, r = n, idx = 1;
    while(l != r){
        int mid = (l + r) / 2;
        if(x > tree[2*idx+1]){
            x -= tree[2*idx+1];
            idx = 2 * idx;
            r = mid;
        }
        else {
            idx = 2 * idx + 1;
            l = mid + 1;
        }
    }
    return l;
}

int main(){

    scanf("%d", &n);

    for(int i=1;i<=n;i++) {
        scanf("%d", &ar[i]);
        pst[i] = ar[i];
    }

    sort(pst + 1, pst + n + 1);

    for(int i=1;i<=n;i++){
        if(num[ pst[i] ] == 0) num[pst[i]] = i;
    }

    for(int i=1;i<=n;i++){
        update_tree(ar[i]);
        if(i % 2 == 1) {
            int x = i/2 + 1;
            printf("%d ", pst[ query1(x) ]);
        }
        else {
            int x = i/2;
            printf("%d ", (pst[ query1(x) ] + pst[ query2(x) ]) / 2);
        }
    }

    return 0;
}