# PBinfo #2534 – Bogdan – Rezolvare C++

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

## Enunț

Bogdan și Ionuț au fost "bff" încă din clasa V, dar acum destinele lor se cam despart…. Pentru a-l consola pe Bogdan, Ionuț i-a făcut o problema cadou. Bogdan nu vrea să-l dezamăgească pe Ionut, așa că vă cere ajutorul pentru a rezolva problema împreuna.

Cerința
Se dă un șir de n elemente, numere naturale. Problema constă în două operații:

1 i val : Elementul de pe poziția i se înlocuiește cu valoarea val.
2 i j : Stabiliți dacă secvența [i,j], din șirul curent, este ordonată  crescător.   

Date de intrare
Fișierul de intrare bogdan.in conține pe prima linie numărul n, iar pe a doua linie n numere naturale separate prin spații. Pe a treia linie a fișierului se afla numărul O, care reprezintă numărul de operații. Pe următoarele O linii se vor afla operațiile.

Date de ieșire
Fișierul de ieșire bogdan.out va conține răspunsurile pentru operațiile de tipul 2, pe linie nouă fiecare.
Dacă răspunsul este afirmativ, se va afișa DA, în caz contrar NU.

Restricții și precizări

1 ≤ n ≤ 100.000
1 ≤ O ≤ 300.000
numerele fiecărui șir curent vor fi mai mici decât 2.000.000.000
Observație importantă : bff = Best Friends Forever

Exemplu:
bogdan.in

6
22 9 2003 14 8 2003
4
2 1 6
1 1 8
2 1 3
2 4 5
bogdan.out

NU
DA
NU

## Cod sursă C++

```cpp
/* Ionut Dobricean
 * Arbori + Parsare
 * 100 puncte
*/
#include <cstdio>
using namespace std;
const int Dim = 100001;
int Tree[Dim * 4], n,O,A[Dim],s;
void Get (int &x);
void Update(int node, int le,int ri,int pos ,int val);
void Query(int node , int le , int ri , int a , int b);
int main() {
	freopen("bogdan.in","r",stdin);
	freopen("bogdan.out","w", stdout);
	Get(n);
	for ( int i = 1; i <= n; ++i) {
		Get(A[i]);
		if( A[i] < A[i-1] )
			Update(1,1,n,i,1);
		else
			Update(1,1,n,i,0);
		}
	Get(O);
	int type, x, y;
	for ( int i = 1; i <= O; ++i) {
		Get(type), Get(x), Get(y);
		if ( type == 1) {
			A[x] = y;
			{
            if ( A[x] < A[x-1])
				Update(1,1,n,x,1);
			else
				Update(1,1,n,x,0);
            }
			if( A[x+1] < A[x] )
				Update(1,1,n,x+1,1);
			else
				Update(1,1,n,x+1,0);
		}
		else {
			s = 0;
			Query(1,1,n,x + 1,y);
			if ( s == 0 )
				printf("DA\n");
			else
				printf("NU\n");
			}
		}
	return 0;
}
void Update(int node, int le,int ri,int pos ,int val) {
	if(le == ri) {
		Tree[node] = val;
		return ;
	}
	int mj = (le + ri) / 2;
	if( pos <= mj)
		Update(node * 2, le, mj , pos , val);
	else
		Update(node * 2 + 1 , mj + 1 , ri , pos , val);
	Tree[node] = Tree[node * 2]  + Tree[node * 2 + 1];
}
void Query(int node , int le , int ri , int a , int b){
    if(a <= le and b >= ri) {
        s += Tree[node];
    return ;
    }
	int mj = (le + ri) / 2;
	if(a <= mj)
		Query(2 * node, le , mj, a , b);
	if(b > mj)
		Query(2 * node + 1, mj + 1 , ri ,a , b);
}
const int Lim = 1000001;
int u =  Lim - 1;
char S[Lim];
void Next () {
    if (++u == Lim)
        std::fread(S, 1, Lim, stdin), u = 0;
}
void Get (int &x) {
	for (; S[u] < '0' || S[u] > '9'; Next());
	for (x = 0; S[u] >= '0' and S[u] <= '9'; Next())
		x = x * 10 + S[u] - '0';
}
```

## Resurse

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