203. 중앙값 측정

백준

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

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

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

2. C++

세그먼트 트리

참고

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int a[250001], tree[1000001];
const int maxi = 65536;
 
// idx번째 리프노드를 diff만큼 추가하는 업데이트
void update(int node, int st, int ed, int idx, int diff) {
    if (st == ed) { tree[node] += diff; return; }
    int mid = (st + ed) >> 1;
    if (idx <= mid) update(2 * node, st, mid, idx, diff);
    else update(2 * node + 1, mid + 1, ed, idx, diff);
    tree[node] = tree[2 * node] + tree[2 * node + 1];
}
 
// k번째로 작은 값을 구하는 쿼리
ll mid_Query(int node, int st, int ed, int k) {
    if (st == ed) return st;
    int mid = (st + ed) >> 1;
    ll ans = 0;
    //k번째가 왼쪽개수보다 적다면 그냥 타고 내려감
    if (k <= tree[2 * node]) {
        return mid_Query(2 * node, st, mid, k);
    }
    //왼쪽개수보다 많다면, 왼쪽을 다 채우고 나머지 k-tree[2*node]개부터 시작
    else return mid_Query(2 * node + 1, mid + 1, ed, k - tree[2 * node]);
}
 
int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, k; cin >> n >> k;
    for (int i = 0; i < n; i++) cin >> a[i];
    //처음부터 k-1개 업데이트
    for (int i = 0; i < k - 1; i++) {
        update(1, 0, maxi, a[i], 1);
    }
    ll ans = 0;
    //1개씩 업데이트하고, 값구하고, 1개씩 빼는 과정
    for (int j = k - 1; j < n; j++) {
        //k개 채우기
        update(1, 0, maxi, a[j], 1);
        //중앙값 구하기
        ans += mid_Query(1, 0, maxi, (k + 1) / 2);
        //k개에서 맨앞의 원소 빼기 
        update(1, 0, maxi, a[j - k + 1], -1);
    }
    cout << ans << '\n';
}
 

인덱스 트리

#include <stdio.h>
#include <algorithm>
#define MIN -1
#define PIV (1<<18)
#define MAX 5005

using namespace std;

int N, K;
int tree[PIV * 2], m[PIV * 2];

int query(int i)
{
    int idx = 1;
    while (idx < PIV)
        if (tree[idx *= 2] < i)
            i -= tree[idx++];
    return idx - PIV;
}

void update(int i, int num)
{
    i += PIV;
    tree[i] += num;
    while(i>>=1)
        tree[i] += num;
}

int main()
{

    scanf("%d %d", &N, &K);
    int mid;
    long long ans = 0;
    for (int i = 0; i < K; i++)
        scanf("%d", &m[i]), update(m[i], 1);

    for (int i = 0; i <= N - K; i++)
    {
        mid = query((K + 1) / 2);
        ans += mid;
        update(m[i], -1); // 이전 숫자 카운트는 줄이고
        scanf("%d", &m[i + K]);
        update(m[i + K], 1); // 다음숫자 카운트는 늘림
    }
    printf("%lld\n", ans);
    return 0;
}