O problema cu maxim

[•lupvasile]

Se da un vector de lungime n. Se dau operatii de doua tipuri: 0 a b x (valoarea tuturor numerelor de la v[a] la v este crescuta cu x) si 1 a b (se cere afisarea maximului din subsecventa v[a]..v). In fisierul de intrare sunt date mai multe operatii de acest gen. Imi spuneti va rog cum se rezolva aceasta problema? Multunesc.

[•BLz0r]

Asta e solutia bruta:

Cod:

#include <fstream>
using namespace std;

int v[1005]; //in loc de 1005 pui valoarea maxima a lui N
int main(){
	ifstream fin ("numefisier.in"); //in loc de numefisier.in pui numele fisierului de intrare
	ofstream fout ("numefisier.out"); //in loc de numefisier.out pui numele fisierului de iesire
	
	int n,op,i,j,a,b,x,max,nr;
	
	fin >>n>>op; //n =nr. de elemente; op =nr. de operatii
	
	for (i=1;i<=n;++i) fin>>v[i]; //citesti vectorul
	
	for (i=1;i<=op;++i){
		fin>>nr; //citesti cifra din fata (0 sau 1)
		if (nr==0){ //daca este 0
			fin>>a>>b>>x; //citesti a,b,x
			for (j=a;j<=b;++j) v[j]=v[j]+x; //incrementezi toate valorile cu x
		}
		else{ //daca este 1
			max=-1; //valoarea maxima
			fin >>a>>b; //citesti capetele
			for (j=a;j<=b;++j)
				if (v[j]>max) max=v[j]; //verifici daca nu cumva valoarea este maxima
			fout <<max<<"\n"; //afisezi
		}
	}
	
	return 0;
}

problema se poate rezolva cu metode mai elegante dar daca tie iti trebuie pur si simplu o rezolvare... asta e ok.
daca nu intelegi ceva spune-mi te rog

[•lupvasile]

Iti multumesc. Stiu ca nu am precizat, dar as avea nevoie de cea mai eficienta metoda, o(n^2) e cam mare...

[•PlayLikeNeverB4]

Merge cu arbori de intervale in O(MlogN), unde M = numarul de operatii.

[•BLz0r]

Din pacate nu am timp acum sa implementez cealalta varianta pt ca sunt pe fuga. Poti folosi smenul lui Mars pentru incrementarea valorilor de la a la b cu x si iti poti tine o matrice cu maxime (mat[j]=maximul de la pozitia i la pozitia j in vectorul v) si iti reduce complexitate f mult. Sper ca ai inteles  

[•lupvasile]

Arborii de intervale nu ii stiu....
Nu pot sa imi declar matricea de maxime pentru ca n poate fi mare si matricea ar ocupa prea mult.
Iar in legatura cu Mars, pentru a afla valorile la un moment dat, nu trebuie sa parcurg tot vectorul pana pozitia dorita?

[•PlayLikeNeverB4]

Ce te opreste sa inveti arborii?
Si da, la Mars operatia 0 ia O(1) si operatia 1 O(N).