Cod sursa(job #2924051)

Utilizator Edyci123Bicu Codrut Eduard Edyci123 Data 23 septembrie 2022 19:12:01
Problema Arbori de intervale Scor Ascuns
Compilator cpp-64 Status waiting
Runda Arhiva educationala Marime 1.33 kb
#include <bits/stdc++.h>
#define INFILE "arbint.in"
#define OUTFILE "arbint.out"
#define DIM 100005

using namespace std;

ifstream f(INFILE);
ofstream g(OUTFILE);

int n, m;
int aint[4 * DIM];

void update(int node, int st, int dr, int poz, int val) {

    if (st == dr) {
        aint[node] = val;
        return ;
    }

    int mid = (st + dr) / 2;

    if (mid >= poz) {
        update(2 * node, st, mid, poz, val);
    } else {
        update(2 * node + 1, mid + 1, dr, poz, val);
    }

    aint[node] = max(aint[2 * node], aint[2 * node + 1]);
}

int query(int node, int st, int dr, int stQ, int drQ) {

    if (stQ <= st && dr <= drQ) {
        return aint[node];
    }

    int mid = (st + dr) / 2, r1(0), r2(0);

    if (mid >= stQ) {
        r1 = query(2 * node, st, mid, stQ, drQ);
    } else if (mid <= drQ) {
        r2 = query(2 * node + 1, mid + 1, dr, stQ, drQ);
    }

    return max(r1, r2);
}

int main() {

    f >> n >> m;

    for (int i = 1; i <= n; i++) {
        int x;
        f >> x;
        update(1, 1, n, i, x);
    }

    for (int i = 1; i <= m; i++) {
        int ops, a, b;
        f >> ops >> a >> b;
        if (ops == 1) {
            update(1, 1, n, a, b);
        } else {
            g << query(1, 1, n, a, b) << "\n";
        }
    }

    return 0;
}