티스토리 뷰

알고리즘 관련/BOJ

BOJ)3653 영화 수집

JASON 자손9319 2017. 1. 10. 18:19

문제: icpc.me/3653


순서대로 쌓여있는 DVD가 있을 때 영화를 볼때마다 위에 몇개의 DVD가 쌓여있는지 출력하는 문제이다. 이 때 본 영화는 맨위에 쌓는다고 한다.


우리는 세그먼트 트리의 구간합을 통하여 문제를 해결할 수 있다.


우선 n+m+1개의 노드중 m+1~n+m+1에 해당하는 리프에 1씩 업데이트 시킨다. 이는 n개의 DVD가 m+1부터 순서대로 존재한다는 것을 의미한다.


이 때 i번 DVD는 i+m에 존재한다고 기록해 준 뒤 


i번째 영화위의 DVD의 개수는 1~(i번 DVD의 위치-1)의 구간합으로 구해줄 수 있다.


DVD를 뺐으므로 원래 DVD의 위치는 0으로 갱신해 준 후 맨 위에 DVD를 갱신해 줘야한다.


맨위는 i번째 쿼리를 처리할 때 m+1-i 번째 위치일 것이다. 해당 위치를 DVD의 위치로 갱신해 준 뒤 리프에 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
#include <cstdio>
#include <algorithm>
#include <cstring>
#define MAX_N 100000
using namespace std;
int seg[* MAX_N], a[* MAX_N + 1], t, n, m, v;
int update(int pos, int val, int node, int x, int y) {
    if (y < pos || pos < x)
        return seg[node];
    if (x == y)
        return seg[node] = val;
    int mid = (x + y) >> 1;
    return seg[node] = update(pos, val, node * 2, x, mid) + update(pos, val, node * + 1, mid + 1, y);
}
int query(int lo, int hi, int node, int x, int y) {
    if (y < lo || hi < x)
        return 0;
    if (lo <= x&&<= hi)
        return seg[node];
    int mid = (x + y) >> 1;
    return query(lo, hi, node * 2, x, mid) + query(lo, hi, node * + 1, mid + 1, y);
}
int main() {
    scanf("%d"&t);
    while (t--) {
        memset(a, 0sizeof(a));
        memset(seg, 0sizeof(seg));
        scanf("%d%d"&n, &m);
        int idx = m + 1;
        for (int i = idx; i <= n + m; i++) {
            update(i, 111, n + m);
            a[i - m] = i;
        }
        idx = m;
        for (int i = 0; i < m; i++) {
            scanf("%d"&v);
            printf("%d ", query(1, a[v] - 111, n + m));
            update(a[v], 011, n + m);
            a[v] = idx--;
            update(a[v], 111, n + m);
        }
        printf("\n");
    }
    return 0;
}
cs


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

BOJ)5676 음주 코딩  (0) 2017.01.10
BOJ)12016 라운드 로빈 스케줄러  (0) 2017.01.10
BOJ)3653 영화 수집  (0) 2017.01.10
BOJ)6549 히스토그램에서 가장 큰 직사각형  (0) 2017.01.10
BOJ)5419 북서풍  (7) 2017.01.10
BOJ)1849 순열  (0) 2017.01.10
댓글
댓글쓰기 폼