AtCoder Regular Contest 101 D - Median of Medians

二分答案

然后前缀和+树状数组来判断这个答案是否大于等于数

如果我们对于一个查询，如果小于这个数令为1，大于这个数领为-1

将所有前缀和放在树状数组中，就可以查询所有sum_{l} < sum_{r}的组合

#include <assert.h>

#include <algorithm>

#include <bitset>

#include <climits>

#include <cmath>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <functional>

#include <iomanip>

#include <iostream>

#include <list>

#include <map>

#include <queue>

#include <set>

#include <stack>

#include <vector>

using namespace std;

const int N = 1e5 + 5;

const int INF = 0x3f3f3f3f;

const int MOD = 1e9 + 7;

typedef long long ll;

int A[N];

int B[N];

int C[N];

ll tree[N * 2];

int n;

void Add(int pos, int num) {

    for (int i = pos; i <= 2 * n; i += i & -i) tree[i] += num;

}

ll Sum(int pos) {

    ll ans = 0;

    for (int i = pos; i > 0; i -= i & -i) ans += tree[i];

    return ans;

}

bool solve(int x) {

    memset(tree, 0, sizeof(tree));

    for (int i = 1; i <= n; ++i) {

        if (A[i] >= x)

            C[i] = 1;

        else

            C[i] = -1;

    }

    ll ans = 0;

    Add(n, 1);

    for (int i = 1; i <= n; ++i) {

        C[i] += C[i - 1];

        ans += Sum(C[i] + n);

        Add(C[i] + n, 1);

    }

    //    printf("%d\n", ans);

    return (ans >= (1ll * n * (n + 1) / 4));

}

int main() {

    while (~scanf("%d", &n)) {

        for (int i = 1; i <= n; ++i) {

            scanf("%d", &A[i]);

            B[i] = A[i];

        }

        sort(B + 1, B + n + 1);

        int tot = unique(B + 1, B + n + 1) - B - 1;

        int l = 1;

        int r = tot;

        while (l <= r) {

            int mid = (l + r) >> 1;

            if (solve(B[mid]))

                l = mid + 1;

            else

                r = mid - 1;

        }

        //    for(int i = 1; i <= tot; ++i) printf("%d ", B[i]); printf("\n");

        printf("%d\n", B[r]);

    }

    return 0;

}

巴特西

AtCoder Regular Contest 101 D - Median of Medians

最新文章

热门文章