본문 바로가기
알고리즘

[BOJ9426] 중앙값 측정

by 박정률 2017. 1. 19.

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


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


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


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


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


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


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



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#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], 110, MAX_N-1);
        
    }
    
    for (int i = 0; i < n - k+1; i++) {
        ans += query(nk, 10, MAX_N-1);
        update(trans[i], -110, MAX_N-1);
        update(trans[i + k], 110, MAX_N-1);
        
 
    }
    printf("%lld", ans);
 
 
 
 
}
cs


'알고리즘' 카테고리의 다른 글

codeforces)447b  (0) 2017.12.21
알고리즘)(pow(A,B))mod C 를 logB 시간에 구하는 함수  (0) 2017.11.26
acm-cicpc 수학정복  (2) 2017.09.15
[BOJ1168] 조세퍼스 문제2  (0) 2017.01.22
[BOJ5012} 불만정렬  (0) 2017.01.22