BOJ 14428数列とクエリー16

18547 ワード
セグメントツリー テキストリンク

質問する


BOJ 14428数列とクエリー16
金色I|白駿14428|Python 3 Python池

アルゴリズム#アルゴリズム#


  • セグメントツリーの資料構造を理解することは、容易に解決できる問題です.

  • この問題では、まずセグメントツリーを使用して最適な値を探します.△最高価格を知っていれば、インデックスはもちろん知っています.10868最高価格の問題と非常に似ていますが、最高値ではなく、値のインデックスを出力する必要があります.この場合、index()関数を使用して値のインデックスを検索するには、より長いO(N)時間がかかるため、配列自体に値とインデックスが含まれます.
    • [5, 3, 4, 1, 2]
-> [[5, 1], [3, 2], [4, 3], [1, 4], [2, 5]]

  • 比較値が大きい場合、ターゲットは値ではなくリストになるため、リスト内の0番目のインデックス値のサイズを比較するためにmin()関数を個別に記述します.

  • 親は子供の中に小銭がある.(最大値ではなくインデックスを出力する必要があるため、リストです.)

    • コード#コード#

    import sys
from math import *

input = sys.stdin.readline
INF = sys.maxsize

# 리스트의 대소를 비교하기 위한 사용자정의 min 함수
def min(a : list, b : list) -> list:
    if a[0] > b[0]:
        return b
    else:
        return a

# 세그먼트 트리 생성 함수
def initTree(node, start, end):
    if start == end:
        segtree[node] = values[start]
        return segtree[node]

    mid = (start + end) // 2
    segtree[node] = min(initTree(node * 2, start, mid), initTree(node * 2 + 1, mid + 1, end))
    return segtree[node]


# 세그먼트 트리 쿼리 함수
def query(node, start, end, left, right):
    if start > right or end < left:
        return [INF, INF]

    if left <= start and end <= right:
        return segtree[node]

    mid = (start + end) // 2
    return min(query(node * 2, start, mid, left, right), query(node * 2 + 1, mid + 1, end, left, right))


# 트리 업데이트 함수
def update(node, start, end, index, x):
    if index < start or index > end:
        return [INF, INF]

    if start == end:
        segtree[node] = x
        return

    mid = (start + end) // 2
    update(node * 2, start, mid, index, x)
    update(node * 2 + 1, mid + 1, end, index, x)

    segtree[node] = min(segtree[node * 2], segtree[node * 2 + 1])


N = int(input())

temp = list(map(int, input().split()))
values = [[0, 0] for _ in range(N)]
# 입력 값을 [값, 인덱스] 형태로 변환해 리스트 저장
for i in range(N):
    values[i][0] = temp[i]
    values[i][1] = i + 1

# 세그먼트 트리 사이즈
ts = 1 << (int(ceil(log2(N))) + 1)
segtree = [0] * ts

# 트리 생성
initTree(1, 0, N - 1)

M = int(input())
for _ in range(M):
    A, B, C = map(int, input().split())
	
    # 트리 값 변경
    if A == 1:
        values[B - 1][0] = C
        update(1, 0, N - 1, B - 1, values[B - 1])
	
    # 구간 출력
    else:
        print(query(1, 0, N - 1, B - 1, C - 1)[1])

    結果


    WebView小Demo
    Vue Mixin