题目思路

权值树状数组+二分查找+离散化

题目分析

本来想用堆做的， 刚好跟着树状数组的标签来的，所以写一下树状数组，根据题目可以知道，求的就是区间第k大这一类模型，只不过i为奇数，中位数位置也是知道的，我们可以想到去二分这个位置， 前缀统计数的出现频率，我们是在线处理的，所以前缀和数组需要一直修改，很麻烦，所以用树状数组来维护，剩下的就是离散化+二分了

时间复杂度 $O(nlogn)$

代码

#include <bits/stdc++.h>
// #pragma GCC optimize("Ofast,no-stack-protector,fast-math",3)
#define intceil(a, b) ((a + b - 1) / b)
#define all(_) _.begin(), _.end()
#define fi first
#define se second
#define rep(i, x ,y) for(i = (x); i <= (y); i++)
#define per(i, x, y) for(i = (x); i >= (y); i--)
#define MIN(_) *min_element(all(_))
#define MAX(_) *max_element(all(_))
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef priority_queue<int, vector<int>, greater<int> > xhp;
typedef priority_queue<int, vector<int>, less<int> > dhp;

template<typename tp1,typename tp2>inline void chmx(tp1 &x,const tp2 &y) {x<y?x=y:0;}
template<typename tp1,typename tp2>inline void chmi(tp1 &x,const tp2 &y) {x>y?x=y:0;}
int n, m;
namespace MATH{
    const int M=1000000007;
    // const int M=998244353;
    vector<int>jc,nv,_nv;
    const int fpow(int a,int b){int res=1;for(;b;b>>=1,a=(ll)a*a%M)b&1&&(res=(ll)res*a%M);return res;}
    inline int C(int n,int m){assert(m<=n);return 1ll*jc[n]*nv[m]%M*nv[n-m]%M;}
    inline int P(int n,int m){return 1ll*jc[n]*nv[n-m]%M;}
    inline int D(int n,int m){if(n<0||m<0)return 0;if(!n)return 1;if(!m)return 0;return C(n+m-1,m-1);}
    inline void init(int n){
        jc.resize(n+2);
        jc[0]=jc[1]=1;
        nv=_nv=jc;
        for(int x=2;x<=n;++x){
            jc[x]=1ll*x*jc[x-1]%M;
            _nv[x]=ll(M-M/x)*_nv[M%x]%M;
            nv[x]=1ll*nv[x-1]*_nv[x]%M;
        }
    }
};
namespace BIT{
    #define lowbit(x) (x&(-x))
    vector<ll> tr;
    inline void init(int n){tr.resize(n+2);}
    inline void add(int i,int v){while(i<=n)tr[i]+=v,i+=lowbit(i);}
    inline ll qry(int i){ll ans=0;while(i)ans+=tr[i],i-=lowbit(i);return ans;}
}

//tie()是解除绑定函数,可以用于map,tuple等.
int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int i, j, k, l, r, x, y, z;
    cin >> n;
    vector<int> a(n), b(n); //a是原数组, b是离散化的数组

    for (i = 0; i < n; i++) cin >> a[i];
    b = a;
    sort(all(b));
    b.erase(unique(all(b)), b.end());

    auto find = [&](int x) {
        return (lower_bound(all(b), x) - b.begin() + 1);
    };

    BIT::init(b.size());  

    for (int i = 0; i < n; i++) {
        int pos = find(a[i]);
        BIT::add(pos, 1);  
        if ((i + 1) & 1) { 
            int idx = (i + 1) / 2 + 1;  
            int l = 1, r = b.size();
            while (l < r) {
                int mid = (l + r) / 2;
                if (BIT::qry(mid) >= idx) r = mid;
                else l = mid + 1;
            }      
            cout << b[l - 1] << "\n";  
        }
    }
    return 0;
}