AjM: Pagină nouă: == 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...

2024-06-03T15:50:37Z

Pagină nouă: == 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...

New page

== 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>

2091 - Actualizare Interval, Minim Interval - Revision history