[BOJ9426] 중앙값 측정

n개의 수열이 있을 때 K의 연속 부분 수열의 중앙값의 합을 구하는 문제이다.

앞에서부터 K개의 수를 업데이트 시켜준 뒤에 앞에서 1개 지우고 뒤에서 1개씩 업데이트하면서 중앙값을 구해나가면 된다.

이 떄 중앙값은 앞에서부터 (k+1)/2 번째 수이다.

앞에서부터 K개의 수를 세그먼트 트리에 업데이트 시켜준 후 N까지 1개씩 지우고 업데이트 시켜주면서 중앙값을 구해주면 된다.

중앙값은 앞에서부터 (k+1)/2 수를 찾으면 된다.

이 때 세그먼트트리는 k번째 수를 찾는 문제처럼 각 노드의 값이 1 또는 0 으로 되어있는 sum - segment - tree 를 구현한다.

주의할점 ! 좌표를 기준으로 값을 저장했으니 좌표가 중복될 수 있다. 따라서 업데이트 시에 현재값 +1 또는 -1 로 업데이트한다.

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
const int MAX_N = 250000;
const int MAX_C = 66000;
using namespace std;
int n, k;
int seg[MAX_N * 4];
vector<pair<int,int>> vt;
int temp;
 
int update(int pos, int val, int node, int x, int y) {
    if (pos < x || y < pos)    return seg[node];
    if (x == y)    return seg[node] += val;
    int mid = (x + y) >> 1;
    update(pos, val, node * 2, x, mid);
    update(pos, val, node * 2 + 1, mid + 1, y);
    seg[node] = seg[node * 2] + seg[node * 2 + 1];
}
 
int query(int val, int node, int x, int y) {
    if (x == y)    return x;
    int mid = (x + y) >> 1;
    if (val <= seg[node * 2])
        return query(val, node * 2, x, mid);
    else
        return query(val-seg[node*2], node * 2 + 1, mid + 1, y);
}
int trans[MAX_N + 1];
int main() {
    freopen("input.txt", "r", stdin);
    scanf("%d %d", &n, &k);
    for (int i = 0; i < n; i++) {
    scanf("%d", &temp);
    vt.push_back({ temp,i });
    trans[i] = temp;
    }
    sort(vt.begin(), vt.end());
    int nk = ((k + 1) >> 1) ;
    long long  ans = 0LL;
    for (int i = 0; i < k; i++) {
        update(trans[i], 1, 1, 0, MAX_N-1);
        
    }
    
    for (int i = 0; i < n - k+1; i++) {
        ans += query(nk, 1, 0, MAX_N-1);
        update(trans[i], -1, 1, 0, MAX_N-1);
        update(trans[i + k], 1, 1, 0, MAX_N-1);
        
 
    }
    printf("%lld", ans);
 
 
 
 
}