题目描述

给定一个长度为 N 的非负整数序列 A，对于前奇数项求中位数。

输入格式

第一行一个正整数 N。

第二行 N 个正整数 A1…N​。

输出格式

共 ⌊2N+1​⌋ 行，第 i 行为 A1…2i−1​ 的中位数。

输入输出样例

输入 #1复制

7
1 3 5 7 9 11 6

输出 #1

1
3
5
6

输入 #2复制

7
3 1 5 9 8 7 6

输出 #2

3
3
5
6

---

树状数组 + 离散化 + 二分  ，时间复杂度O(n log n)

离散化：将原始数值映射到1~n的范围内

树状数组：使用树状数组来维护每个离散化后的数值出现的次数

二分：在树状数组上二分查找第k小的数，利用树状数组的前缀和特性

---

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<queue>
#include<deque>
#include<stack>
#include<set>
#include<map>
#include<unordered_set>
#include<unordered_map>
#include<bitset>
#include<tuple>
#define inf 72340172838076673
#define int long long
#define endl '\n'
#define F first
#define S second
#define  mst(a,x) memset(a,x,sizeof (a))
using namespace std;
typedef pair<int, int> pii;const int N = 100086, mod = 998244353;int n, m;
int a[N],e[N];
vector<int> alls;int lowbit(int x) {return x & -x;
}void add(int i, int x) {for (; i <= n; i += lowbit(i)) e[i] += x;
}int sum(int i) {int res = 0;for (; i; i -= lowbit(i)) res += e[i];return res;
}int find(int k) {int l = 0, r = n;while (l + 1 < r) {int mid = l + r >> 1;if (sum(mid) < k) l = mid;else r = mid;}return r;
}void solve() {cin >> n;alls.push_back(0);for (int i = 1; i <= n; i++) {cin >> a[i];alls.push_back(a[i]);}sort(alls.begin(), alls.end());alls.erase(unique(alls.begin(), alls.end()), alls.end());for (int i = 1; i <= n; i++) {a[i] = lower_bound(alls.begin(), alls.end(), a[i]) - alls.begin();}for (int i = 1; i <= n; i++) {add(a[i], 1);if (i & 1) {cout << alls[find((i + 1)>>1)] << endl;}}}signed main() {ios::sync_with_stdio(false);cin.tie(nullptr), cout.tie(nullptr);int T = 1;
// cin >> T;while (T--) solve();return 0;
}