以下代码通过使用二分等算法，可在 $O(nlog^2n)$ 的时间复杂度内

求出一个序列的最大值

代码如下

#include<bits/stdc++.h>
#pragma GCC optimize(2)
#define cur 300010
#define lowbit(x) ((x) & (-x))
using namespace std;

int N, ans = -1;
int A[300005];
int l = 0, r = 1000000000;
long long target;
int C[600055];

void update(int idx, int val){
	for (int i = idx; i <= cur + N; i += lowbit(i)){
		C[i] += val;
	}
}

int query(int idx){
	int res = 0;
	for (int i = idx; i; i -= lowbit(i)){
		res += C[i];
	}
	return res;
}

bool check(int x){
	memset(C, 0, sizeof(C));
	int nowval = 0;
	long long cnt = 0; // how much [i, j] med <= x
	for (int i = 1; i <= N; i ++){
		int tmp = (A[i] <= x) ? -1 : 1;
		update(cur + nowval, 1);
		nowval += tmp;
		cnt += i - query(cur + nowval - 1);
	}
	return cnt >= target;
}

int main(){
#ifndef ONLINE_JUDGE
    freopen("../data.in", "r", stdin);
    freopen("../data.out", "w", stdout);
#endif

	scanf("%d", &N);
	target = 1LL * (N + 1) * N / 2;
	for (int i = 1; i <= N; i ++){
		scanf("%d", &A[i]);
	}
	while (l <= r){
		int mid = (l + r) >> 1;
		if (check(mid)){
			ans = mid;
			r = mid - 1;
		}else{
			l = mid + 1;
		}
	}
	printf("%d\n", ans);

    return 0;
}

可以试试看