[백준] 9426 중앙값 측정

중앙값은 말 그대로 중앙에 있는 값이다

K개 중에서 (K+1)/2번째 에 있는 값을 구하면 된다

이 문제는 세그먼트트리로 풀 수 있다.

온도가 0~65536 까지니까 넉넉하게 66666까지 잡고

온도가 측정될 때 마다 tree에서 온도를 +1 해준다

그리고 K개 이상이면 i-k번째를 -1 하고 중앙값을 찾는다!

- 세그먼트트리에서 K번째를 찾기 위해서는 

나의 왼쪽 자식인 tree[node*2]와 값을 비교해보면 된다

만약 K가 같거나 작다면 왼쪽에 있는 것이니까 왼쪽으로가고

아니라면 오른쪽으로 가는데 K에서 왼쪽만큼을 빼고 가야한다!

그래야 전체적으로 볼때 K번째를 찾을 수 있다.

소스코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
#define ll long long
#define MAXN 66666
 
void update(vector<int>&tree, int node, int start, int end, int index, int val) {
    if (index <start || index> end) return;
    if (start == end) {
        tree[node] += val; return;
    }
    update(tree, node * 2, start, (start + end) / 2, index, val);
    update(tree, node * 2 + 1, (start + end) / 2 + 1, end, index, val);
    tree[node] = tree[node * 2] + tree[node * 2 + 1];
}
 
int kth(vector<int>&tree, int node, int start, int end, int k) {
    if (start == end) return start;
    else {
        if (k <= tree[node*2]) return kth(tree, node * 2, start, (start + end) / 2, k);
        else return kth(tree, node * 2 + 1, (start + end) / 2 + 1, end, k - tree[node * 2]);
    }
}
int main() {
    int n, k; scanf(" %d %d", &n, &k);
    int h = (int)ceil(log2(MAXN + 1));
    int tree_size = (1 << (h + 1));
    int cnt = (k + 1) / 2;
    vector<int> tree(tree_size,0);
    vector<int> a(n + 1,0);
    ll ans = 0;
    for (int i = 1; i <= n; i++) {
        scanf(" %d", &a[i]);
        update(tree, 1, 0, MAXN, a[i], 1);
        if (i >= k) {
            if(i !=k) update(tree, 1, 0, MAXN, a[i - k], -1);
            int pos = kth(tree, 1, 0, MAXN, cnt);
            ans += (ll)pos;
        }
    }
    printf("%lld\n", ans);
}