Cod sursa(job #910324)

Utilizator PatrikStepan Patrik Patrik Data 10 martie 2013 20:03:58
Problema Arbori de intervale Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.8 kb
    #include<cstdio>
    #include<iostream>
    using namespace std;
    #define MAX 400002
    int N , M , V[MAX/2] , A[MAX]  , x , y , z;

    void citire();
    void build(int n , int l , int r);
    void update(int n , int l , int r , int a );
    int query(int n , int l , int r , int a , int b);

    int main()
    {
        citire();
        build(1,1,N);
        for(int i = 1 ; i <= M  ; ++i )
        {
            scanf("%d%d%d" , &x , &y , &z);
            if(x == 0)
                printf("%d\n",query(1,1,N,y,z));
            else
            {
                V[y] = z;
                update(1,1,N,y);
            }
        }
    }

    void citire()
    {
        freopen("arbint.in" , "r" , stdin );
        freopen("arbint.out" , "w" , stdout );
        scanf("%d%d" , &N , &M);
        for(int i = 1 ; i<=N ; ++i )
            scanf("%d" , &V[i]);
    }

    void build(int n , int l , int r )
    {
        if(l == r)A[n] = V[l];
        else
        {
            int m = (l+r)/2;
            build(2*n,l,m);
            build(2*n+1,m+1,r);
            A[n] = max(A[2*n],A[2*n+1]);
        }
    }

    int query(int n , int l , int r , int a , int b)
    {
        int maxx = 0;
        if(a <=l && b >= r)return A[n];
        else
        {
            int m = (l+r)/2;
            if(a<=m)
                maxx = query(2*n,l,m,a,b);
            if(b > m)
                maxx = max(maxx,query(2*n+1,m+1,r,a,b));
        }
        return maxx;
    }

    void update(int n ,int l , int r , int a )
    {
        if(l==r && l==a)A[n] = V[a];
        if(l == r)return;
        else
        {
            int m = (l+r)/2;
            update(2*n,l,m,a);
            update(2*n+1,m+1,r,a);
            A[n] = max(A[2*n],A[2*n+1]);
        }
    }