Cod sursa(job #2729193)

Utilizator cyg_dawidDavid Ghiberdic cyg_dawid Data 24 martie 2021 13:35:44
Problema Arbori de intervale Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.27 kb
#include <fstream>
#include <algorithm>

std::ifstream fin ("arbint.in");
std::ofstream fout ("arbint.out");

int const nmax = 100000;
int const aintdim = (nmax << 2);
int aint[aintdim + 10];

void update (int nod, int st, int dr, int poz, int val) {
    if (st == dr) {
        aint[nod] = val;
        return;
    }
    int med = (st + dr) >> 1;
    if (poz <= med)
        update ((nod << 1), st, med, poz, val);
    else
        update (((nod << 1) + 1), med + 1, dr, poz, val);
    aint[nod] = std::max(aint[(nod << 1)], aint[((nod << 1) + 1)]);
}

int query (int nod, int st, int dr, int l, int r) {
    if (l <= st && dr <= r)
        return aint[nod];
    int med = (st + dr) >> 1;
    if (r <= med)
        return query ((nod << 1), st, med, l, r);
    if (med < l)
        return query (((nod << 1) + 1), med + 1, dr, l, r);
    return std::max(query ((nod << 1), st, med, l, r), query (((nod << 1) + 1), med + 1, dr, l ,r));
}

int main() {
    int n, m;
    fin >> n >> m;
    for (int i = 1; i <= n; i++) {
        int x;
        fin >> x;
        update (1, 1, n, i, x);
    }
    while (m--) {
        int c, x, y;
        fin >> c >> x >> y;
        if (c == 1)
            update (1, 1, n, x, y);
        else
            fout << query (1, 1, n, x, y) << "\n";
    }
    return 0;
}