Cod sursa(job #2770341)

Utilizator AlexMariMarinescu Alexandru AlexMari Data 20 august 2021 16:28:15
Problema Arbori de intervale Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.47 kb
#include<bits/stdc++.h>
using namespace std;
ifstream fin("arbint.in");
ofstream fout("arbint.out");

int n,t;

struct Aint
{
    int v[400005];
    void update(int nod,int poz,int val,int st,int dr)
    {
        if(st==dr)
        {
            v[nod]=val;
            return;
        }
        else
        {
            int mijl=(st+dr)/2;
            if(poz<=mijl)
                update(2*nod,poz,val,st,mijl);
            else
                update(2*nod+1,poz,val,mijl+1,dr);
            v[nod]=max(v[2*nod],v[2*nod+1]);
        }
    }
    int query(int nod,int query_st,int query_dr,int st,int dr)
    {
        if(query_st==st&&query_dr==dr)
            return v[nod];
        int mijl=(st+dr)/2;
        if(query_dr<=mijl)
            return query(2*nod,query_st,query_dr,st,mijl);
        else
            if(query_st>=mijl+1)
              return query(2*nod+1,query_st,query_dr,mijl+1,dr);
        else
        {
            int val1=query(2*nod,query_st,mijl,st,mijl);
            int val2=query(2*nod+1,mijl+1,query_dr,mijl+1,dr);
            return max(val1,val2);
        }
    }
}aint;

int main()
{
    fin>>n>>t;
    for(int i=1; i<=n; i++)
    {
        int x;
        fin>>x;
        aint.update(1,i,x,1,n);
    }
    while(t--)
    {
        int op,a,b;
        fin>>op>>a>>b;
        if(op==0)
            fout<<aint.query(1,a,b,1,n)<<'\n';
        else
            aint.update(1,a,b,1,n);
    }
    return 0;
}