Cod sursa(job #2483821)

Utilizator meriniucrMeriniuc Razvan- Dumitru meriniucr Data 30 octombrie 2019 13:10:35
Problema Arbori de intervale Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.88 kb
#include <fstream>
#include <vector>
#include <iostream>

int vals[100005];
int tree[200012];

void
build(int beg,
      int end,
      int index)
{
    if (beg == end)
    {
        tree[index] = vals[beg];
        return;
    }

    int mid = (beg + end) / 2;
    build(beg, mid, 2 * index);
    build(mid + 1, end, 2 * index + 1);

    tree[index] = std::max(tree[2 * index], tree[2 * index + 1]);
}

int
query(int beg,
      int end,
      int a,
      int b,
      int index)
{
    if (beg == a and end == b)
    {
        return tree[index];
    }

    int mid = (beg + end) / 2;

    if (mid < a)
    {
        return query(mid + 1, end, a, b, 2 * index + 1);
    }
    else if (mid >= b)
    {
        return query(beg, mid, a, b, 2 * index);
    }
    
    return std::max(query(beg, mid, a, mid, 2 * index),
                    query(mid + 1, end, mid + 1, b, 2 * index + 1));
}

void
update(int pos,
       int val,
       int beg,
       int end,
       int index)
{
    if (beg == end)
    {
        tree[index] = val;
        return;
    }

    int mid = (beg + end) / 2;

    if (mid >= pos)
    {
        update(pos,
               val,
               beg,
               mid,
               2 * index);
    }
    else
    {
        update(pos,
               val,
               mid + 1,
               end,
               2 * index + 1);
    }

    tree[index] = std::max(tree[2 * index], tree[2 * index + 1]);
}

int main()
{
    std::fstream  fin("arbint.in");
    std::ofstream fout("arbint.out");

    int N, M;

    fin >> N >> M;

    for (int i = 1; i <= N; i++)
    {
        fin >> vals[i];
    }

    build(1, N, 1);

    for (int i = 0, op, a, b; i < M; i++)
    {
        fin >> op;
        fin >> a >> b;

        if (0 == op)
        {
            fout << query(1, N, a, b, 1) << std::endl;
        }
        else
        {
            update(a, b, 1, N, 1);
        }
    }

    return 0;
}