# PBinfo #2094 – Actualizare Element, CMMDC Interval – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: deivid

## Enunț

Se dă un șir de numere asupra căruia se pot face două tipuri de operații: actualizare a unui element (schimbarea valorii sale) și interogarea unui interval de indici (determinarea celui mai mare divizor comun pentru valorile aflate între cei doi indici, inclusiv).

Cerința
Afișați răspunsul la fiecare interogare.

Date de intrare
Prima linie a fisierului aecmmdci.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 găsesc câte 3 numere naturale separate prin câte un spațiu: T A B. Dacă T = 1 operația este de interogare iar A și B sunt capetele inrervalului. Dacă T = 2 operația este de actualizare cu semnificația: elementul de pe poziția A devine B.

Date de ieșire
Fișierul aecmmdci.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 cele de la operațiile de actualizare, sunt strict pozitive <= 2000000000

Exemplu:
aecmmdci.in

5
2 12 6 9 8
3
1 2 4
2 4 2
1 2 4
aecmmdci.out

3
2

## Cod sursă C++

```cpp
#include <fstream>
#include <climits>
#define DIM 100010
#define INF INT_MAX
using namespace std;
ifstream fin ("aecmmdci.in");
ofstream fout("aecmmdci.out");
int A[4*DIM];
int n, m, a, b, t, i, minim;
int cmmdc(int a, int b) {
    int r;
    while (b) {
        r = a%b;
        a = b;
        b = r;
    }
    return a;
}
void build(int nod, int st, int dr) {
    if (st == dr) {
        fin>>A[nod];
    } else {
        int mid = (st + dr)/2;
        build(2*nod, st, mid);
        build(2*nod+1, mid+1, dr);
        A[nod] = cmmdc(A[2*nod], A[2*nod+1]);
    }
}
void query(int nod, int st, int dr, int a, int b) {
    if (a <= st && dr <= b) {
        if (minim == INF)
            minim = A[nod];
        else
            minim = cmmdc(minim, A[nod]);
    } else {
        int mid = (st + dr)/2;
        if (a <= mid)
            query(2*nod, st, mid, a, b);
        if (b > mid)
            query(2*nod+1, mid+1, dr, a, b);
    }
}
void update(int nod, int st, int dr, int a, int b) {
    if (st == dr) {
        A[nod] = b;
    } else {
        int mid = (st + dr)/2;
        if (a <= mid)
            update(2*nod, st, mid, a, b);
        if (a > mid)
            update(2*nod+1, mid+1, dr, a, b);
        A[nod] = cmmdc(A[2*nod], A[2*nod+1]);
    }
}
int main () {
    fin>>n;
    build(1, 1, n);
    fin>>m;
    for (int i=1;i<=m;i++) {
        fin>>t>>a>>b;
        if (t == 1) {
            minim = INF;
            query(1, 1, n, a, b);
            fout<<minim<<"\n";
        } else {
            update(1, 1, n, a, b);
        }
    }
    return 0;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/2094)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/2094/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-2094/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)