E1. Median on Segments (Permutations Edition)

题目链接

Codeforces Round #496 (Div. 3)--E1. Median on Segments (Permutations Edition)

题解

中档题。题意大概是给定一个数字序列,求出其中有几个区间满足中位数为给定的值。
首先对整个序列进行预处理,判断从头到当前大于给定值的数字减去小于给定值的数字及当前数字出现次数,预处理后可以在O(1)的时间复杂度内判断任意区间大于给定值的数字减去小于给定值的数字。其次处理任意区间内给定值的数量,假设为x,则大于给定值的数字减去小于给定值的数字为[x-n+1,x+n]为符合条件的区间。如此可以在O(x)的复杂度内求出当前位置作为右端点的区间数量。

代码

#include <iostream>
#include <map>
#include <algorithm>
using namespace std;
int n, m;
int a[200005], mnum(0), now(0);
long long ans;
map<int, map<int, int>>maps;
int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        if (a[i] > m) {
            now++;
            maps[mnum][now]++;
        }
        else if (a[i] < m) {
            now--;
            maps[mnum][now]++;
        }
        else if (a[i] == m) { 
            mnum++;
            maps[mnum][now]++;
        }
    }
    maps[0][0]++;
    now = mnum = 0;
    for (int i = 1; i <= n; i++) {
        if (a[i] > m) {
            now++;
        }
        else if (a[i] < m) {
            now--;
        }
        else if (a[i] == m)mnum++;
        for (int j = 0; j < mnum; j++) {
            for (int k = -(mnum-j); k <= (mnum-j)-1; k++) {
                ans += maps[j][now + k];
            }
        }
    }
    cout << ans;
}

标签: sortings

添加新评论