5922번: Above the Median

https://www.acmicpc.net/problem/5922

$O(n)$

간단히 x 이상인 수가 절반이상인 구간의 수를 구하면 된다.
a[i] = h[i]가 x이상이면 1, x미만이면 -1이라 하면
임의의 [i,j]에 대해 a[i...j] 합이 0이상인 경우 [i,j]는 x이상인 수가 절반이상이다.
따라서 누적합 s[i]=sum(a[1...i])을 이용하여 증가하는 j마다 i<j인 임의의 i에 대해 s[i]<=s[j]인 i의 수를 빠르게 찾으면 된다.

여기서부터는 펜윅트리 같은 자료구조를 이용해서 풀 수도 있지만,
i가 증가함에 따라 s[i]의 변화량이 최대 1 밖에 되지 않는다는 점을 착안하여 prefix sum을 이용하여 O(n)에 해결할 수 있다.

#include<cstdio>
int n, x, a[200001], p, t;
long long r, s = 1;
int main() {
    scanf("%d%d", &n, &x);
    a[p = n] = 1;
    while (n--) {
        scanf("%d", &t);
        t < x ? s -= a[p--] : s += a[++p];
        a[p]++; r += s++;
    }
    printf("%lld", r);
    return 0;
}