[BOJ] 14428 - 수열과 쿼리 16 (Python, JavaScript)

 

 

아이디어

 

세그먼트 트리로 구간 내 최솟값과 인덱스를 저장해두고 변경이나 출력이 필요한 구간에 대해 빠르게 처리한다.

 

 

풀이 #1 (Python)

 

import sys

input = sys.stdin.readline

INF = int(1e9)

def solution():

    def minimum(s, e):
        min_val = tree[s]
        while s <= e:
            if s%2:
                if tree[s] < min_val:
                    min_val = tree[s]
                s += 1
            if e%2 == 0:
                if tree[e] < min_val:
                    min_val = tree[e]
                e -= 1
            s >>= 1
            e >>= 1
        return min_val[1]

    def modify(idx):
        while idx > 1:
            if tree[idx] < tree[idx^1]:
                tree[idx>>1] = tree[idx]
            else:
                tree[idx>>1] = tree[idx^1]
            idx >>= 1

    N = int(input())
    n = 1
    while n < N:
        n *= 2
    tree = [(INF, n*2) for _ in range(n*2)]
    A = tuple(map(int, input().split()))
    for i in range(N):
        tree[i+n] = (A[i], i+1)
    for i in range(n-1, 0, -1):
        if tree[i<<1] < tree[(i<<1)^1]:
            tree[i] = tree[i<<1]
        else:
            tree[i] = tree[(i<<1)^1]
    M = int(input())
    res = []
    for _ in range(M):
        t, i, j = map(int, input().split())
        if t == 1:
            tree[i+n-1] = (j, i)
            modify(i+n-1)
        else:
            res.append(f'{minimum(i+n-1, j+n-1)}')
    print('\n'.join(res))

solution()

 

 

 

풀이 #2 (JavaScript)

 

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().split('\n');

function solution() {
    
    function minimum(i, j) {
        let [s, e] = [i, j];
        let minVal = tree[s];
        while (s <= e) {
            if (s%2) {
                if (tree[s][0] < minVal[0]) minVal = tree[s];
                else if (tree[s][0] === minVal[0] && tree[s][1] < minVal[1]) minVal = tree[s];
                s += 1;
            }
            if (e%2 === 0) {
                if (tree[e][0] < minVal[0]) minVal = tree[e];
                else if (tree[e][0] === minVal[0] && tree[e][1] < minVal[1]) minVal = tree[e];
                e -= 1;
            }
            s >>= 1;
            e >>= 1;
        }
        return minVal[1];
    }
    
    function modify(idx) {
        while (idx > 1) {
            if (tree[idx][0] < tree[idx^1][0]) tree[idx>>1] = tree[idx];
            else if (tree[idx][0] > tree[idx^1][0]) tree[idx>>1] = tree[idx^1];
            else if (tree[idx][1] < tree[idx^1][1]) tree[idx>>1] = tree[idx];
            else tree[idx>>1] = tree[idx^1];
            idx >>= 1;
        }
    }
    
    const N = Number(input[0]);
    let n = 1;
    while (n < N) n *= 2;
    var tree = [];
    for (let i=0; i<n*2; i++) tree.push([Number.MAX_SAFE_INTEGER, n*2]);
    const A = input[1].split(' ').map(Number);
    for (let i=0; i<N; i++) tree[i+n] = [A[i], i+1];
    for (let i=n-1; i>0; i--) {
        if (tree[i<<1][0] <= tree[(i<<1)^1][0]) tree[i] = tree[i<<1];
        else tree[i] = tree[(i<<1)^1];
    }
    const M = Number(input[2]);
    let res = [];
    for (let k=3; k<M+3; k++) {
        const [t, i, j] = input[k].split(' ').map(Number);
        if (t === 1) {
            tree[i+n-1] = [j, i];
            modify(i+n-1);
        }
        else res.push(minimum(i+n-1, j+n-1));
    }
    console.log(res.join('\n'));
}

solution();