Cod sursa(job #2567349)

Utilizator alex23alexandru andronache alex23 Data 3 martie 2020 16:45:41
Problema Arbori de intervale Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.63 kb
#include <vector>

int update(std::vector<int>& tree, int index, int value, int start, int end) {
    int li = start, ls = end, poz = 0;

    while ((li < ls)) {
        int m = (li + ls) / 2;
        if (index <= m) {
            ls = m;
            poz = 2 * poz + 1;
            if (tree[poz] < value) tree[poz] = value;
        }
        else{
            li = m + 1;
            poz = 2 * poz + 2;
            if (tree[poz] < value) tree[poz] = value;
        }
    }

    tree[poz] = value;
    while (poz) {
        int t = (poz - 1) / 2;
        tree[t] = std::max(tree[2 * t + 1], tree[2 * t + 2]);
        poz = (poz - 1) / 2;
    }

    return 0;
}

int query(std::vector<int>& tree, int index, int start, int finish, int left, int right) {
    if ((start <= left) && (right <= finish)) {
        return tree[index];
    }

    int m = (left + right) / 2;
    if (start <= m) return query(tree, 2 * index + 1, start, finish, left, m);
    if (finish >= m + 1) return query(tree, 2 * index + 2, start, finish, m + 1, right);
}

#ifndef TESTING
int main() {
    FILE *f = fopen("arbint.in", "r");
    FILE *g = fopen("arbint.out", "w");

    int N, M, x;
    fscanf(f, "%d %d", &N, &M);
    std::vector<int> a((2 << (N - 1)) - 1);

    for (int i = 0; i < N; ++i) {
        fscanf(f, "%d", &x);
        update(a, i, x, 0, N - 1);
    }

    for (int i = 0; i < M; ++i) {
        int x, y, z;
        fscanf(f, "%d %d %d", &x, &y, &z);
        if (x) {
            update(a, y - 1, z, 0, N - 1);
        }
        else {
            fprintf(g, "%d\n", query(a, 0, y - 1, z - 1, 0, N - 1));
        }
    }

    fclose(f);
    fclose(g);

    return 0;
}
#endif