标签：std const int tree 中位数 P1168
离散化，线段树
#include
using namespace std;
const int N = 1e5 + 7;
int a[N], tree[N << 4], hs[N];
void add(int x, int i, int l, int r){
tree[i] ++;
if(l == r) return;
int mid = (l + r) >> 1;
if(x <= mid) add(x, i << 1, l, mid);
else add(x, i << 1 | 1, mid + 1, r);
}
int query(int m, int i, int l, int r){
if(l == r) return hs[l];
int mid = (l + r) >> 1;
if(tree[i << 1] >= m) return query(m, i << 1, l, mid);
else return query(m - tree[i << 1], i << 1 | 1,mid + 1, r);
}
int main(){
int n;
scanf("%d", &n);
for(int i = 1;i <= n;i ++)
scanf("%d", &a[i]), hs[i] = a[i];
sort(hs + 1, hs + n + 1);
int t = unique(hs + 1, hs + n + 1) - hs - 1;
int p = lower_bound(hs + 1, hs + t + 1, a[1]) - hs;
add(p, 1, 1, t);
printf("%d\n", query(1, 1, 1, t));
for(int i = 3;i <= n;i += 2){
p = lower_bound(hs + 1, hs + t + 1, a[i]) - hs;
add(p, 1, 1, t);
p = lower_bound(hs + 1, hs + t + 1, a[i - 1]) - hs;
add(p, 1, 1, t);
printf("%d\n", query(i/2 + 1, 1, 1, t));
}
return 0;
}
标签：std,
const,
int,
tree,
中位数,
P1168
From： https://www.cnblogs.com/loser--QAQ/p/16892418.html