Cod sursa(job #2541581)

Utilizator pepsiM4A1Ozturk Arif pepsiM4A1 Data 8 februarie 2020 16:57:31
Problema Arbori de intervale Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.75 kb
#include <iostream>
const int nmax=100004;
using namespace std;
int v[nmax];
int n,m;
int arb[4*nmax];
///daca sunt la nodul i, fiul din stanga va fi la pozitia 2*i
///daca sunt la nodul i, fiul din dreapta va fi la pozitia 2*i+1
void update(int st,int dr,int pos,int nod)
{
    ///pos = pozitia la care dau update
    ///st = capatul din stanga al subsegmentului
    ///dr = capatul din dreapta al subsegmentului
    ///nod = nodul actual
    if(st==dr) arb[nod] = v[pos];
    else
    {
        int mij=(st+dr)/2;
        if(pos<=mij) update(st,mij,pos,2*nod);
        else update(mij+1,dr,pos,2*nod+1);
        arb[nod] = max(arb[2*nod],arb[2*nod+1]);
    }
}
int query(int st,int dr, int p1,int p2,int nod)
{
    ///p1 = capatul din stanga al intrebarii
    ///p2 = capatul din dreapta al intrebarii
    ///st = capatul din stanga al subsegmentului
    ///dr = capatul din dreapta al subsegmentului
    ///nod = nodul actual
    if(st==p1&&dr==p2) return arb[nod];
    else
    {
        int mij=(st+dr)/2;
        if(p2<=mij) return query(st,mij,p1,p2,2*nod);
        else if(p1>mij) return query(mij+1,dr,p1,p2,2*nod+1);
        else
        {
            return max(query(st,mij,p1,mij,2*nod),
                       query(mij+1,dr,mij+1,p2,2*nod+1));
        }
    }

}
int main()
{
    freopen("arbint.in","r",stdin);
    freopen ("arbint.out","w",stdout);
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&v[i]);
    for(int i=1;i<=n;i++) update(1,n,i,1);
    for(int i=1;i<=m;i++)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        if(a==0) printf("%d\n",query(1,n,b,c,1));
        else
        {
            v[b]=c;
            update(1,n,b,1);
        }
    }
    return 0;
}