Cod sursa(job #2345431)

Utilizator cosceexcosceex cosceex Data 16 februarie 2019 12:42:34
Problema Arbori de intervale Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.46 kb
#include <cstdio>
#define nmax 100000
using namespace std;

int a_interv[nmax * 4];

inline int maxim(int a,int b){
    if(a<b)
        return b;
    return a;
}

void Update(int nod , int low , int high , int poz , int val){
    if(low==high)
        a_interv[ nod ] = val;
    else{
        int mij = ( low + high ) >> 1;
        if( poz <= mij )
            Update( nod *2 , low , mij , poz ,val);
        else
            Update( nod *2 + 1 , mij+1 , high , poz , val);
        a_interv[ nod ] = maxim( a_interv[ nod * 2 ] , a_interv[ nod * 2 + 1 ]);
    }
}


int Q(int nod , int l , int r , int a ,  int b){
    if(a <= l && b >= r)
        return a_interv[nod];
    int mij=(r+l)>>1;
    int A=0,B=0;
    if(b > mij)
        B=Q(nod * 2 + 1 , mij + 1 , r , a , b);
    if(a <= mij)
        A=Q(nod * 2 , l , mij , a , b);
        //printf("%d %d %d %d %d %d\n", nod, l, r, a, b, a_interv[nod]);
    return maxim(A,B);
}

int main(){
    int n,m,x;
    freopen("arbint.in","r",stdin);
    scanf("%d%d",&n,&m);
    for(int i = 1; i <= n; i++){
        scanf("%d",&x);
        Update(1,1,n,i,x);
    }

    for (int i = 1; i <= n; ++i) {
        printf("%d ", Q(1, 1, n, i, i));
    }
    int o,a,b;
    freopen("arbint.out","w",stdout);
    for(int i = 1; i <= m; i++){
        scanf("%d%d%d",&o,&a,&b);
        if(o==1)
            Update(1,1,n,a,b);
        else
        printf("%d\n",Q(1,1,n,a,b));
    }
    return 0;
}