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

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>