Cod sursa(job #1288345)

Utilizator hasmasandragosHasmasan Dragos hasmasandragos Data 8 decembrie 2014 19:15:15
Problema Arbori de intervale Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.96 kb
#include <fstream>
using namespace std;

ifstream f("arbint.in");
ofstream g("arbint.out");

const int nmax=100005;

int arb[4*nmax+66],n,val,op,be/*gin*/,en/*d*/,poz,maxim,t,i;

void Updt (int nod ,int stanga , int dreapta)
{
    int mijloc;
    if (stanga==dreapta)
    {
     arb[nod]=val;
     return;
    }
    else
     mijloc=(stanga+dreapta)/2;
     if (poz<=mijloc) Updt(2*nod,stanga,mijloc); // de ce 2*nod si 2*nod+1 ? pt ca orice nod n (care nu este terminal) are minim 2 fii , exact ca un heap , care sunt pe pozitiile 2*n si 2*n+1
     else Updt(2*nod+1,mijloc+1,dreapta);
    arb[nod]=max(arb[2*nod],arb[2*nod+1]);
}

void Quer (int nod, int stanga , int dreapta)
{
    int mijloc;
    if (be <= stanga && dreapta <= en) // daca ne incadram in interval
    {
        if (arb[nod]>maxim) maxim=arb[nod]; // de ce nu afisam direct maximul ? ei bine , nu tot timpul vom putea "prinde" perfect intervalul [a,b] ; ex: sa zicem ca avem intevalul de la 3 la 7 , si noi suntem la pasul in care avem nodul intervalului [3,5] , daca returnam chiar acum maximul , se omit punctele 6 si 7 , ceea ce nu este bine.
        return;
    }
    mijloc=(stanga+dreapta)/2;
    if (be<=mijloc) Quer(2*nod,stanga,mijloc); // practic , daca nu ne afalam in partea dorita a arborelui , tot mergem mai adanc , pana ce ajungem la capatul dorit , ex: daca suntem pe nodul intevralului [3,5] , si ne trebuie sa afisam maximul din intervalul [2,5] , mergem in stanga;
    if (mijloc<en)  Quer(2*nod+1,mijloc+1,dreapta);
}

int main()
{
    f>>n>>t;
    for (i=1;i<=n;i++)
     {
         f>>val;
         poz=i;
         Updt(1,1,n);
     }
    while (t--)
    {
        f>>op;
        if (op==1)
        {
            f>>poz>>val;
            Updt (1,1,n);
        }
        else
        {
            f>>be>>en;
            maxim=-1;
            Quer(1,1,n);
            g<<maxim<<'\n';
        }
    }
    f.close();
    g.close();
    return 0;
}