티스토리 뷰

알고리즘 관련/BOJ

BOJ)9426 중앙값 측정

JASON 자손9319 2017. 1. 11. 00:48

문제: icpc.me/9426


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


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


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


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
#include <cstdio>
#include <algorithm>
#define MAX_N 250001
#define MAX 65536
using namespace std;
typedef long long ll;
ll seg[* MAX_N], a[MAX_N], n, k, res;
ll update(ll pos, ll val, ll node, ll x, ll y) {
    if (y < pos || pos < x)
        return seg[node];
    if (x == y)return seg[node] += val;
    ll mid = (x + y) >> 1;
    return seg[node] = update(pos, val, node * 2, x, mid) + update(pos, val, node * + 1, mid + 1, y);
}
ll query(ll val, ll node, ll x, ll y) {
    ll mid = (x + y) >> 1;
    if (x == y)return x;
    if (seg[node * 2>= val)return query(val, node * 2, x, mid);
    return query(val - seg[node * 2], node * + 1, mid + 1, y);
}
int main() {
    scanf("%lld%lld"&n, &k);
    for (int i = 0; i < n; i++) {
        scanf("%lld"&a[i]);
    }
    for (int i = 0; i < k - 1; i++
        update(a[i], 110, MAX - 1);
    for (int i = k - 1; i < n; i++) {
        update(a[i], 110, MAX - 1);
        res += query((k + 1/ 210, MAX - 1);
        update(a[i - k + 1], -110, MAX - 1);
    }
    printf("%lld", res);
    return 0;
}
cs


'알고리즘 관련 > BOJ' 카테고리의 다른 글

BOJ)3002 아날로그 다이얼  (0) 2017.01.11
BOJ)1168 조세퍼스 문제2  (0) 2017.01.11
BOJ)9426 중앙값 측정  (7) 2017.01.11
BOJ)5676 음주 코딩  (0) 2017.01.10
BOJ)12016 라운드 로빈 스케줄러  (0) 2017.01.10
BOJ)3653 영화 수집  (0) 2017.01.10
댓글
  • 프로필사진 질문드려요 혹시 세그먼트 트리를 어떻게 구성하셨는지 알려주실수있나요? 구간합에대한 segment tree는 공부했는데 어떤 값을 채우고 어떻게 닶을 유추해나가는지 이해가 안되서요 2017.03.06 14:13
  • 프로필사진 JASON 자손9319 부족한 설명 죄송합니다 ㅜㅜ.. 현재 세그먼트 트리에 저장되는 값들은 구간의 합이 저장이 됩니다.

    아마 쿼리부분이 낯설으실수도 있으실텐데 쿼리는 현재 저장된 값들 중 K번째 수를 이분탐색으로 logN시간에 찾아주는 함수입니다. 현재 제가 찾는 값이 val이고 왼쪽 자식 노드가 val보다 작거나 같다면 K번째 수는 왼쪽 자식노드에 있으니 왼쪽으로 보내주고.. 이런식으로 K번째 수가 몇번째 세그먼트에 담겨있는지 찾아주는 쿼리입니다
    2017.03.06 14:26 신고
  • 프로필사진 JASON 자손9319 이렇게 K번째 수찾기를 이용하여 저희는 중앙값을 찾기를 원하기 때문에 중앙값을 찾기 위한 구간을 세그먼트 트리에 업데이트 해준 후 K번째 수가 몇번째 세그먼트에 존재하는지를 계산해주면서 답을 계산합니다 2017.03.06 14:27 신고
  • 프로필사진 JASON 자손9319 메인함수에서 쿼리를 처리할 때 첫번째 업데이트는 추가할 구간이고 쿼리에 대한 답을 더해준 후 앞의 구간의 업데이트를 해제해주면서 전체구간의 중간값을 구해주는 것입니다. 이해가 되셨을지 모르겠네요 ㅜㅜ 2017.03.06 14:28 신고
  • 프로필사진 감사합니다 ㅎㅎ공부할게많네요..세그먼트트리에 입력받은수들이 들어갈거라 예상했는데 갯수처럼업데이트가되더라구요..
    ㅎㅎ조금더보겠습니다~ 말씀주신데로 쿼리문이 이해가 안가네요~
    감사합니다
    2017.03.06 16:23
  • 프로필사진 JASON 자손9319 K번째 수를 찾는 쿼리에 대한 문제는 https://www.acmicpc.net/problem/1321 한번 풀어보시면 도움이 될거 같아요 ㅜㅜ

    2017.03.06 16:30 신고
  • 프로필사진 놀라고기가막혀 감사합니다 ㅠㅠㅠ 2020.05.19 20:43
댓글쓰기 폼