Cod sursa(job #2444716)

Utilizator vladadAndries Vlad Andrei vladad Data 1 august 2019 10:51:31
Problema Arbori de intervale Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.39 kb
#include<bits/stdc++.h>
using namespace std;
ifstream f("arbint.in");
ofstream g("arbint.out");
int n, aint[400001], v[100001], a, b, val, tip, ans, q;
void build(int nod, int st, int dr)
{
    if(st==dr)
    {
        aint[nod]=v[st];
        return;
    }
    int mij=st+(dr-st)/2;
    build(nod*2, st, mij);
    build(nod*2+1, mij+1, dr);
    aint[nod]=max(aint[nod*2], aint[nod*2+1]);
}
int query(int nod, int st, int dr, int L, int R)
{
    int A, B;
    if(dr<L || st>R)
        return 0;
    if(L<=st && dr<=R)
        return aint[nod];
    int mij=st+(dr-st)/2;
    A=query(nod*2, st, mij, L, R);
    B=query(nod*2+1, mij+1, dr, L, R);
    return max(A, B);
}
void update(int nod, int st, int dr, int poz, int val)
{
    if(st==dr)
    {
        aint[nod]=val;
        return;
    }
    int mij=st+(dr-st)/2;
    if(poz<=mij)
        update(nod*2, st, mij, poz, val);
    else
        update(nod*2+1, mij+1, dr, poz, val);
    aint[nod]=max(aint[nod*2], aint[nod*2+1]);
}
int main()
{
    f>>n>>q;
    for(int i=1; i<=n; i++)
        f>>v[i];
    build(1, 1, n);
    for(; q; q--)
    {
        f>>tip;
        if(tip==0)
        {
            f>>a>>b;
            g<<query(1, 1, n, a, b)<<'\n';
        }
        else
        {
            f>>a>>b;
            update(1, 1, n, a, b);
        }
    }
    f.close();
    g.close();
    return 0;
}