Pagini recente » Borderou de evaluare (job #2629564) | Cod sursa (job #1072398)
#include <fstream>
using namespace std;
const int MAXN = 131072;//cica lica putere 2 mai rapid, dar merge si cu MAXN
int arbore[2 * MAXN];
int n;
int localizare_frunza(int p, int a, int b, int f)
{
int mij = (a + b) / 2;
if (a == b)
return p;
if (f <= mij)
return localizare_frunza(2 * p, a, mij, f);
else return localizare_frunza(2 * p + 1, mij + 1, b, f);
}
void actualizare_recursiva(int p)
{
arbore[p] = max(arbore[2 * p], arbore[2 * p + 1]);
if (p == 1)
return;
actualizare_recursiva(p / 2);
}
void actualizare_arbore(int f, int val)
{
int pf = localizare_frunza(1,1,n,f);
arbore[pf] = val;
actualizare_recursiva(pf / 2);
}
int interogare_recursiva(int p, int a, int b, int s, int d)
{
if (s <= a && b <= d)
return arbore[p];
if (b < s || d < a)
return -1;
int mij = (a + b) / 2;
return max(interogare_recursiva(2 * p, a, mij, s, d), interogare_recursiva(2 * p + 1, mij + 1, b, s, d));
}
inline int interogare_arbore(int s, int d)
{
return interogare_recursiva(1, 1, n, s, d);
}
void citire()
{
int nr;
int m;
int test,a,b;
ifstream in("arbint.in");
ofstream out("arbint.out");
in >> n >> m;
for (int i = 1;i <= n;++i)
{
in >> nr;
actualizare_arbore(i,nr);
}
for (int i = 1;i <= m;++i)
{
in >> test >> a >> b;
if (test == 0)
out << interogare_arbore(a,b) << '\n';
else actualizare_arbore(a,b);
}
}
int main()
{
citire();
return 0;
}