반응형

https://www.acmicpc.net/problem/15816

 

15816번: 퀘스트 중인 모험가

첫째 줄에 지금까지 달성한 퀘스트의 개수 N이 주어진다. (1 ≤ N ≤ 1,000,000) 둘째 줄에 지금까지 달성한 퀘스트들의 번호 Q1 ... QN 까지의 N개의 수가 주어진다. (−1,000,000,000 ≤ Q[i] ≤ 1,000,000,000, Q

www.acmicpc.net

 

 

[ 문제풀이 ]

이 문제를 풀기 전에 다음 글을 먼저 읽고 오시는 것을 추천드립니다.

https://rudalsd.tistory.com/364

 

[ 자료구조 ] 비재귀 세그먼트 트리 (Segment Tree)

1. 비재귀 세그먼트 트리 (Segment Tree) 재귀 세그먼트 트리에서는 항상 루트노드부터 시작했었습니다. 하지만 비재귀 세그먼트 트리에서는 반대로 리프노드부터 시작합니다. 2. 비재귀 세그먼트

rudalsd.tistory.com

 

1. list 배열에 완료한 퀘스트를 저장하고, vector<int> quest에 입력으로 주어진 모든 퀘스트 항목들을 push 하고 중복을 제거합니다.

 

2. for문으로 arr배열을 돌면서 lower_bound를 활용하여 해당 퀘스트가 몇번 째 순서인지 확인하고, segmentTree를 업데이트해줍니다.

 

3. query를 이용하여 R - L + 1 - (L ~ R 구간합)을 통해 답을 출력합니다.

 

[ 소스코드 ]

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#include<iostream>
#include<vector>
#include<algorithm>
 
using namespace std;
 
struct query {
    int cmd;
    int L, R;
};
 
int N, M;
vector<int> quest;
query arr[1000000];
int segTree[6000000];
int list[1000000];
 
void updateTree(int idx)
{
    while (idx != 0) {
        segTree[idx]++;
        idx >>= 1;
    }
}
 
int getTree(int L, int R)
{
    int ret = 0;
 
    while (L <= R) {
        if (L & 1) {
            ret += segTree[L];
            L++;
        }
        if (~R & 1) {
            ret += segTree[R];
            R--;
        }
 
        L >>= 1;
        R >>= 1;
    }
 
    return ret;
}
 
int main()
{
    scanf("%d", &N);
 
    for (int i = 0; i < N; i++) {
        int Q;
        scanf("%d", &Q);
 
        list[i] = Q;
        quest.push_back(Q);
    }
 
    scanf("%d", &M);
 
    for (int i = 0; i < M; i++) {
        int cmd;
        scanf("%d", &cmd);
 
        if (cmd == 1) {
            int X;
            scanf("%d", &X);
 
            quest.push_back(X);
            arr[i] = { cmd,X,0 };
        }
        else {
            int L, R;
            scanf("%d %d", &L, &R);
 
            quest.push_back(L);
            quest.push_back(R);
            arr[i] = { cmd,L,R };
        }
    }
 
    sort(quest.begin(), quest.end());
    quest.erase(unique(quest.begin(), quest.end()), quest.end());
    int n = quest.size();
 
    for (int i = 0; i < N; i++) {
        auto idx = lower_bound(quest.begin(), quest.end(), list[i]) - quest.begin();
        updateTree(n + idx);
    }
 
    for (int i = 0; i < M; i++) {
        int cmd = arr[i].cmd;
        int L = arr[i].L;
        int R = arr[i].R;
 
        if (cmd == 1) {
            auto idx = lower_bound(quest.begin(), quest.end(), L) - quest.begin();
            updateTree(n + idx);
        }
        else {
            auto Lidx = lower_bound(quest.begin(), quest.end(), L) - quest.begin();
            auto Ridx = lower_bound(quest.begin(), quest.end(), R) - quest.begin();
 
            printf("%d\n", R - L + 1 - getTree(n + Lidx, n + Ridx));
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지

'백준' 카테고리의 다른 글

[ 백준 ] 14449번 - Balanced Photo (C++)  (0) 2023.06.09
[ 백준 ] 11962번 - Counting Haybales (C++)  (0) 2023.06.08
[ 백준 ] 17398번 - 통신망 분할 (C++)  (0) 2023.06.06
[ 백준 ] 16168번 - 퍼레이드 (C++)  (0) 2023.06.05
[ 백준 ] 12893번 - 적의 적 (C++)  (0) 2023.06.04

+ Recent posts

티스토리툴바