Cod sursa(job #3373690)

Utilizator MateiDiaconuDiaconu Matei Stefan MateiDiaconu Data 7 noiembrie 2026 16:44:10
Problema Arbori de intervale Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.1 kb
#include <iostream>

using namespace std;

#define MAXN 100000

int v[MAXN];
int aint[2 * MAXN];

inline int leftChild(int node){
    return node + 1;
}
inline int rightChild(int node, int nleft, int mid){
    return node + 2 * (mid - nleft + 1);
}

void build(int node, int left, int right){
    if(left == right){
        aint[node] = v[left];
    }
    else{
        int mid = (left + right) / 2;

        build(leftChild(node), left, mid);
        build(rightChild(node, left, mid), mid + 1, right);

        aint[node] = max(aint[leftChild(node)], aint[rightChild(node, left, mid)]);
    }
}

int query(int node, int nleft, int nright, int qleft, int qright){
    if(qleft <= nleft && qright >= nright){
        return aint[node];
    }

    int rez = 0, mid = (nleft + nright) / 2;

    if(qleft <= mid){
        rez = max(rez, query(leftChild(node), nleft, mid, qleft, qright));
    }

    if(qright > mid){
        rez = max(rez, query(rightChild(node, nleft, mid), mid + 1, nright, qleft, qright));
    }

    return rez;
}

void update(int node, int nleft, int nright, int pos, int val){
    if(nleft == nright){
        aint[node] = val;
    }
    else{
        int mid = (nleft + nright) / 2;

        if(pos <= mid){
            update(leftChild(node), nleft, mid, pos, val);
        }
        else{
            update(rightChild(node, nleft, mid), mid + 1, nright, pos, val);
        }

        aint[node] = max(aint[leftChild(node)], aint[rightChild(node, nleft, mid)]);
    }
}

int main()
{
    FILE *fin, *fout;
    fin = fopen("arbint.in", "r");
    fout = fopen("arbint.out", "w");

    int n, m, i, op, a, b;

    fscanf(fin, "%d%d", &n, &m);

    for(i = 0; i < n; i++){
        fscanf(fin, "%d", &v[i]);
    }

    build(0, 0, n - 1);

    for(i = 0; i < m; i++){
        fscanf(fin, "%d%d%d", &op, &a, &b);

        if(op == 0){
            fprintf(fout, "%d\n", query(0, 0, n - 1, a - 1, b - 1));
        }
        else{
            update(0, 0, n - 1, a - 1, b);
        }
    }

    fclose(fin);
    fclose(fout);
    return 0;
}