以下代码通过使用二分等算法，可在 $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;
}

可以试试看

欢迎来做题目!

链接