Luogu p1168 median

Original link
Look, the label is a segment tree , Tree array , Previously learned segment tree , Tree array and so on are almost forgotten , I thought it would be a long war , I didn't expect to see an immortal when I read the solution . Using dynamic arrays vector and upper_bound The function passed
I know for the first time insert add upper_bound Can sort . This saves us the most time-consuming sorting problem

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll INF=0x7fffffff;
const int N = 1e6+5;
const int mod=100003;
int main()
{
    
    ios::sync_with_stdio(false);
    vector<int> v;
    int n,x;
    cin>>n;
    for(int i=1;i<=n;i++){
    
        cin>>x;
        v.insert(upper_bound(v.begin(),v.end(),x),x);
        if(i%2==1)
            cout<<v[(i-1)/2]<<endl;
    }
    return 0;
}