树状数组求调悬关

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 1e2;
int n,a[N],b[N],k[N];
int c[N];
inline int lowbit(int x) {
    return x & -x;
}
inline void add(int x) {
    while(x <= n) {
        c[x] ++;
        x += lowbit(x);
    }
    return;
}
inline int sum(int x) {
    int res = 0;
    while(x) {
        res += c[x];
        x -= lowbit(x);
    }
    return res;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin >> n;
    for(int i = 1;i <= n;i ++) {
        cin >> a[i];
        b[i] = a[i];
    }
    sort(b + 1,b + 1 + n);//原数组的有序数组
    int len = unique(b + 1,b + 1 + n) - (b + 1);
    for(int i = 1;i <= n;i ++) a[i] = lower_bound(b + 1,b + 1 + len,a[i]) - b;//离散化无序数组
    for(int i = 1;i <= n;i ++) k[i] = a[i];
    sort(k + 1,k + 1 + n);//离散化有序数组
    for(int i = 1,j = 1;i <= n;i += 2,j ++) {
        int l = 1,r = n,mid,ans;
        add(a[i]);
        if(i > 1) add(a[i - 1]);
        while(l <= r) {//二分
            mid = l + r >> 1;
            if(sum(k[mid]) >= j) ans = mid,r = mid - 1;
            else l = mid + 1;
        }
        cout << b[ans] << '\n';
    }
    return 0;
}