2243번: 사탕상자
첫째 줄에 수정이가 사탕상자에 손을 댄 횟수 n(1≤n≤100,000)이 주어진다. 다음 n개의 줄에는 두 정수 A, B, 혹은 세 정수 A, B, C가 주어진다. A가 1인 경우는 사탕상자에서 사탕을 꺼내는 경우이다.
www.acmicpc.net
사탕의 맛이 1 ~ 1000000 까지 있습니다.
저는 맛을 인덱스로 하여 세그먼트 트리를 사용하여 구간 합을 구현하였습니다.
A가 1일 때, B는 꺼낼 사탕의 순위입니다.
A가 2일 때, B는 넣는 사탕의 맛이고, C는 갯수이며 양수면 넣는 경우, 음수면 빼는 경우입니다.
A = 2가 들어오면 B 인덱스에 C만큼 추가하면 되겠고
A = 1이 들어오면 사탕의 순위를 이분탐색으로 찾습니다.
이분탐색은 세그먼트 트리의 값을 이용하여 범위를 찾습니다.
x가 왼쪽 자식노드의 수보다 작거나 같으면 (tree[node * 2] >= x) l ~ m 범위로 내려가고 (더 낮은 구역을 탐색)
x가 왼쪽 자식노드의 수보다 크면 (tree[node * 2 < x) m + 1 ~ r의 범위로 내려갑니다. (더 높은 구역을 탐색)
이 때 m + 1 ~ r의 범위로 이동할 때 오른쪽 자식노드의 순위를 판단해야 하기때문에 x - tree[node * 2] 한 값을 보내줍니다.
마지막으로 l == r 구역에 도달하면 사탕을 한개 빼줘야하므로 update를 해주고 찾은 인덱스를 리턴해줍니다.
|
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
|
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static final int MAX = 1000000;
static int tree[] = new int[(MAX + 1) * 4];
static int N;
static void update(int node, int s, int e, int idx, int diff) {
if (idx < s || idx > e)
return;
if (s == e) {
tree[node] += diff;
return;
}
tree[node] += diff;
int m = (s + e) / 2;
update(node * 2, s, m, idx, diff);
update(node * 2 + 1, m + 1, e, idx, diff);
}
static int binarysearch(int node, int l, int r, int x) {
if (l == r) {
update(1, 1, MAX, l, -1);
return l;
}
int m = (l + r) / 2;
if (tree[node * 2] >= x)
return binarysearch(node * 2, l, m, x);
else
return binarysearch(node * 2 + 1, m + 1, r, x - tree[node * 2]);
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
StringBuffer sb = new StringBuffer();
N = Integer.parseInt(st.nextToken());
while (N-- > 0) {
st = new StringTokenizer(br.readLine());
int type = Integer.parseInt(st.nextToken());
if (type == 1) {
int a = Integer.parseInt(st.nextToken());
sb.append(binarysearch(1, 1, MAX, a)).append("\n");
} else {
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
update(1, 1, MAX, a, b);
}
}
System.out.println(sb.toString());
}
}
|
cs |
'algorithm > SegmentTree' 카테고리의 다른 글
| boj 14438 수열과 쿼리 17 (0) | 2021.02.21 |
|---|---|
| boj 13537 수열과 쿼리 1 (0) | 2021.02.21 |
| boj 6549 히스토그램에서 가장 큰 직사각형 (0) | 2021.02.19 |
| boj 2104 부분배열 고르기 (0) | 2021.02.19 |
| boj 2042 구간 합 구하기 (0) | 2021.01.23 |