티스토리 뷰

알고리즘 관련/BOJ

BOJ)14428 수열과 쿼리 16

JASON 자손9319 2017. 3. 9. 16:28

문제: icpc.me/14428


i j 가 주어질 때 Ai ~ Aj 까지의 최솟값의 인덱스를 출력하는 문제이다.


세그먼트 트리를 이용하여 구간의 가장 작은 위치의 인덱스를 저장해주면 된다.



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
#include <cstdio>
#include <algorithm>
#define INF 987654321
using namespace std;
int n, m, seg[400000], x, y, z, a[100001];
int uquery(int pos, int node, int x, int y) {
    if (pos < x || y < pos)return seg[node];
    if (x == y)return seg[node] = x;
    else {
        int mid = (x + y) >> 1;
        int q1 = uquery(pos, node * 2, x, mid);
        int q2 = uquery(pos, node * + 1, mid + 1, y);
        if (q1 == -&& q2 == -1)return -1;
        else if (q1 == -1)return seg[node] = q2;
        else if (q2 == -1)return seg[node] = q1;
        else if (a[q1] <= a[q2])return seg[node] = q1;
        else return seg[node] = q2;
    }
}
int query(int lo, int hi, int node, int x, int y) {
    if (y < lo || hi < x)return -1;
    if (lo <= x&&<= hi)return seg[node];
    int mid = (x + y) >> 1;
    int q1 = query(lo, hi, node * 2, x, mid);
    int q2 = query(lo, hi, node * + 1, mid + 1, y);
    if (q1 == -1)return q2;
    if (q2 == -1)return q1;
    if (a[q1] <= a[q2])return q1;
    return q2;
}
int main() {
    scanf("%d"&n);
    for (int i = 1; i <= n; i++) {
        scanf("%d"&a[i]);
    }
    for (int i = 1; i <= n; i++)
        uquery(i, 11, n);
    scanf("%d"&m);
    for (int i = 0; i < m; i++) {
        scanf("%d%d%d"&x, &y, &z);
        if (x == 1) {
            a[y] = z;
            uquery(y, 11, n);
        }
        else
            printf("%d\n", query(y, z, 11, n));
    }
    return 0;
}
cs


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

BOJ)4716 풍선  (0) 2017.03.11
BOJ)11407 책 구매하기3  (0) 2017.03.11
BOJ)14428 수열과 쿼리 16  (0) 2017.03.09
BOJ)3640 제독  (0) 2017.03.09
BOJ)11409 열혈강호 6  (0) 2017.03.09
BOJ)11408 열혈강호5  (0) 2017.03.09
댓글
댓글쓰기 폼