題目描述

給定一個長度為?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;
}