Vizualizare sursă pentru „2091 - Actualizare Interval, Minim Interval”

== Enunt ==
Se dă un șir de numere asupra căruia se pot face două tipuri de operații: actualizare a unui interval (schimbarea valorii tuturor elementelor aflate între două poziții date) și interogarea unui interval (determinarea celei mai mici valori aflate între două poziții date).
== Cerinţa ==
Afișați răspunsurile la fiecare interogare.
== Date de intrare ==
Prima linie a fisierului aimi.in conține un număr N, ce reprezintă lungimea șirului dat. Linia a doua, conține, separate prin câte un spațiu elementele șirului dat. Pe linia a treia se află un număr M ce reprezintă numărul de operații ce se efectuează asupra șirului dat. Pe fiecare din următoarele M linii se află descrierea câte unei operații astfel: interogările sub forma 1 A B, cerându-se minimul elementelor aflate între pozițiile A și B inclusiv, sau 2 A B X, semnificând faptul că toate elementele de pe poziții de la A la B inclusiv primesc valoarea X.
== Date de ieșire ==
Fișierul aimi.out conține pe câte o linie răspunsul la căte o operațe de tip 1, în ordinea în care acestea apar în datele de intrare.
== Restricţii şi precizări ==
* 1 ≤ N ≤ 100000
* 1 ≤ M ≤ 100000
* 1 ≤ A ≤ B ≤ N
* elementele șirului dat sunt indexate de la 1
* elementele șirului dat precum și valorile X sunt de tip int, pozitive
== Exemplu ==
; aimi.in
 5
 1 6 4 3 9
 3
 1 2 4
 2 2 3 2
 1 2 4
; aimi.out
 3
 2
<br>

== Rezolvare ==
<syntaxhighlight lang="python" line>
class SegmentTree:
    def __init__(self, nums):
        self.n = len(nums)
        self.tree = [float('inf')] * (4 * self.n)
        self.build(nums, 0, 0, self.n - 1)
        
    def build(self, nums, idx, left, right):
        if left == right:
            self.tree[idx] = nums[left]
            return
        mid = (left + right) // 2
        self.build(nums, 2 * idx + 1, left, mid)
        self.build(nums, 2 * idx + 2, mid + 1, right)
        self.tree[idx] = min(self.tree[2 * idx + 1], self.tree[2 * idx + 2])
    
    def update(self, idx, left, right, pos, val):
        if left == right == pos:
            self.tree[idx] = val
            return
        mid = (left + right) // 2
        if pos <= mid:
            self.update(2 * idx + 1, left, mid, pos, val)
        else:
            self.update(2 * idx + 2, mid + 1, right, pos, val)
        self.tree[idx] = min(self.tree[2 * idx + 1], self.tree[2 * idx + 2])
    
    def query(self, idx, left, right, q_left, q_right):
        if q_left <= left and right <= q_right:
            return self.tree[idx]
        if q_right < left or right < q_left:
            return float('inf')
        mid = (left + right) // 2
        left_min = self.query(2 * idx + 1, left, mid, q_left, q_right)
        right_min = self.query(2 * idx + 2, mid + 1, right, q_left, q_right)
        return min(left_min, right_min)

def main():
    with open("aimi.in", "r") as fin, open("aimi.out", "w") as fout:
        N = int(fin.readline())
        nums = list(map(int, fin.readline().split()))
        tree = SegmentTree(nums)
        
        M = int(fin.readline())
        for _ in range(M):
            op = list(map(int, fin.readline().split()))
            if op[0] == 1:
                left, right = op[1] - 1, op[2] - 1
                min_val = tree.query(0, 0, N - 1, left, right)
                fout.write(f"{min_val}\n")
            else:
                pos, val = op[1], op[2]
                tree.update(0, 0, N - 1, pos - 1, val)

if __name__ == "__main__":
    main()

</syntaxhighlight>