Berza

Na berzi je za određenu deonicu data njena cena za svaki datum. Treba omogućiti efikasnu promenu cene za određeni datum, nalaženje maksimalne cene za dati vremenski interval, kao i broj puta koliko je taj maksimum dostignut.

Opis ulaza

Sa standardnog ulaza unose se dva cela broja \(n\) i \(q\) iz intervala \([1, 100000]\). Nakon toga sa najpre učitava niz od \(n\) celih brojeva koji predstavljaju vrednosti određene deonice po datumima, a zatim i \(q\) upita oblika:

Opis izlaza

Za svaki upit tipa \(m\) na standardni izlaz ispisati vrednost i broj pojavljivanja maksimuma u odgovarajućem segmentu.

Primer

Ulaz

Izlaz

Rešenje

Opis glavnog rešenja

Ideja rešenja je da od niza cena napravimo segmentno stablo, što nam omogućava da na oba upita odgovorimo u vremenu \(O(\log n)\). Bitno je napomenuti da u čvorovima čuvamo uređeni par \((m, c)\), gde je \(m\) maksimum segmenta koji čvor pokriva, a \(c\) broj pojavljivanja tog maksimuma.

Ako pretpostavimo da je u korenu levog, odnosno desnog, podstabla maksimalni element \(m_l\) koji se javlja \(c_l\) puta, odnosno \(m_r\) koji se javlja \(c_r\) puta, onda u korenu stabla maksimalni element mora biti \(\max \{m_l, m_r\}\) koji će se javljati \(c_l\) ili \(c_r\) puta u zavisnosi od toga da li je \(m_l > m_r\) ili \(m_l < m_r\). Ukoliko je \(m_l = m_r\), onda u korenu stabla maksimalni element mora biti \(m_l\) koji se javlja \(c_l + c_r\) puta. Za operaciju \(\max\) neutral je \(-\infty\), dok je neutral za operaciju \(+\) nula. Zbog toga je par koji predstavlja neutral \((-\infty, 0)\). Sada je jednostavno implementirati algoritam.

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility> 
#include <limits>
#include <cmath>

using namespace std;

void build(vector<pair<int, int>> &tree, const vector<int> &arr,
           const int i, const int start, const int end) 
{
    if (start == end) {
        tree[i] = { arr[start], 1 };
        return;
    }

    int mid = (start + end) / 2;

    build(tree, arr, 2 * i + 1, start,   mid);
    build(tree, arr, 2 * i + 2, mid + 1, end);

    const auto [max_left,  count_left]  = tree[2 * i + 1];
    const auto [max_right, count_right] = tree[2 * i + 2];

    if (max_left > max_right) {
        tree[i] = { max_left,  count_left  };
    } else if (max_left < max_right) {
        tree[i] = { max_right, count_right };
    } else { // max_left == max_right
        tree[i] = { max_left,  count_left + count_right };
    }
}

void build(vector<pair<int, int>> &tree, const int n, const vector<int> &arr)
{
    build(tree, arr, 0, 0, n - 1);
}

pair<int, int> query(const vector<pair<int, int>> &tree, 
                     const int i, const int start, const int end, 
                     const int l, const int r) 
{
    if (r < start || l > end) {
        return { numeric_limits<int>::min(), 0 };
    }

    if (l <= start && r >= end) {
        return tree[i];
    }

    int mid = (start + end) / 2;

    auto [max_left,  count_left]  = query(tree, 2 * i + 1, start,   mid, l, r);
    auto [max_right, count_right] = query(tree, 2 * i + 2, mid + 1, end, l, r);

    if (max_left > max_right) {
        return { max_left, count_left };
    } else if (max_left < max_right) {
        return { max_right, count_right };
    } else { // max_left == max_right
        return { max_left,  count_left + count_right };
    }
}

pair<int, int> query(const vector<pair<int, int>> &tree, const int n, 
                     const int l, const int r)
{
    return query(tree, 0, 0, n - 1, l, r);
}

void update(vector<pair<int, int>> &tree, 
            const int i, const int start, const int end, 
            const int ind, const int val) 
{
    if (start == end) {
        tree[i] = { val, 1 };
        return;
    } 

    int mid = (start + end) / 2;
    
    if (ind <= mid) {
        update(tree, 2 * i + 1, start,   mid, ind, val);
    } else {
        update(tree, 2 * i + 2, mid + 1, end, ind, val);
    }

    const auto [max_left,  count_left]  = tree[2 * i + 1];
    const auto [max_right, count_right] = tree[2 * i + 2];

    if (max_left > max_right) {
        tree[i] = { max_left,  count_left  };
    } else if (max_left < max_right) {
        tree[i] = { max_right, count_right };
    } else { // max_left == max_right
        tree[i] = { max_left,  count_left + count_right };
    }
}

void update(vector<pair<int, int>> &tree, const int n, 
            const int ind, const int val)
{
    update(tree, 0, 0, n - 1, ind, val);
}

int main(void) 
{
    int n, q; cin >> n >> q;

    vector<int> arr(n);
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    const int height = ceil(log2(n));
    const int size = 2 * pow(2, height) - 1;

    vector<pair<int, int>> tree(size); 

    build(tree, n, arr);

    while (q--) {
        char op; cin >> op;
        if (op == 'u') {
            int ind, val; cin >> ind >> val;
            update(tree, n, ind, val);
        } else if (op == 'm') {
            int l, r; cin >> l >> r;
            const auto [max, count] = query(tree, n, l, r);
            cout << max << " " << count << endl;
        } 
    }

    return 0;
}