Cod sursa(job #623641)

Utilizator cipri_tomCiprian Tomoiaga cipri_tom Data 20 octombrie 2011 15:08:50
Problema Datorii Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.38 kb
#include <fstream>
using namespace std;

ifstream fin("datorii.in");
ofstream fout("datorii.out");

int arb[400005], n, m;
int val, poz, a, b;

void Update ( int nod, int st, int dr); // updateaza nodul nod, pe intervalul [st, dr],
                     					//  pe pozitia poz in sirul zilelor cu valoarea val
int Querry ( int nod, int st, int dr);  //returneaza suma din intervalul [a, b] cerut, in functie de
										//nodul curent nod, si intervalul definit de acesta [st, dr]

int main()
{
	fin >> n >> m;
	int x;
	for ( int i = 1; i <= n; ++i )
	{
		fin >> x;
		poz = i;
		val = -x;  //adun pe nod
		Update ( 1, 1, n);
	}
	int c, y;
	for ( int i = 1; i <= m; ++i )
	{
		fin >> c >> x >> y;
		if ( c )
		{
			a = x;
			b = y;
			fout << Querry ( 1, 1, n) << '\n';
		}
		else
		{
			poz = x;
			val = y;
			Update ( 1, 1, n);
		}
	}
	
	return 0;
}

void Update ( int nod, int st, int dr )
{
	if ( st == dr )
	{
		arb[nod] -= val;  //updatez frunza, achitand valoarea
		return;
	}
	int mij = (st + dr) / 2;
	if ( poz <= mij )
		Update ( 2 * nod, st, mij);
	else
		if ( mij < poz)
			Update ( 2 * nod + 1, mij + 1, dr);
	arb[nod] = arb[2 * nod] + arb[2 * nod + 1];
}

int Querry (int nod, int st, int dr)
{
	if ( st >= a && dr <= b )
		return arb[nod];
	int mij = (st + dr) / 2;
	int s = 0;
	if ( a <= mij )
		s += Querry ( 2 * nod, st, mij);
	if ( b > mij )
		s += Querry ( 2 * nod + 1, mij + 1, dr);
	return s;
}