Neka je dat niz \(a\) dužine \(n\). Postoje 2 vrste upita koje se mogu vršiti nad ovim nizom, \(u\) i \(m\). Za svaki od \(m\) upita je potrebno odrediti maksimalan proizvod 2 broja u nekom segmentu tog niza. Za svaku od \(u\) upita je potrebno ažurirati vrednost nekog elementa u nizu.
Sa standardnog ulaza se unosi vrednost \(n\) a zatim i \(n\) vrednosti koje predstavljaju elemente niza. Zatim se unosi vrednost \(q\) koja predstavlja broj upita. U narednih \(q\) linija se unose upiti oblika:
-\(u \, i \, v\) - vrednost elementa na poziciji \(i\) u nizu \(A\) postaviti na \(v\)
-\(m \, l \, r\) - odrediti maksimalni proizvod 2 elementa u intervalu \([l, r]\) u nizu \(A\)
Za svaki upit tipa \(m\) na standardni izlaz ispisati maksimalni proizvod 2 elementa u odgovarajućem segmentu.
10 1 4 12 6 7 39 23 42 10 15 6 m 0 2 m 3 8 u 4 50 m 2 7 u 9 30 m 7 9
48 1638 2100 1260
Dve vrednosti čiji je proizvod maksimalan u nekom segmentu su maksimalni element, i drugi maksimalni element u tom segmentu. Dakle, rešenje zadatka se može svesti na nalaženje maksimuma i najvećeg elementa manjeg od maksimuma u segmentu nizu.
Prvi korak je formirati segmentno stablo, pri čemu u svakom čvoru čuvamo upravo maksimalni element \(m_1\) i drugi maksimalni element \(m_2\). U listovima kao maksimalni element čuvamo element niza, dok ćemo kao drugi maksimalni za taj segment čuvati minimalnu moguću vrednost integera. Pitanje je kako ažuriramo vrednosti za unutrašnje čvorove. Iz levog potomka dobijamo njegov maksimalni (\(m_1^{left}\)) i drugi maksimalni element (\(m_2^{left}\)), dok iz desnog potomka dobijamo iste podatke za odgovarajući segment, odnosno \(m_1^{right}\) i \(m_2^{right}\). Maksimalni element u segmentu koji pokriva unutrašnji čvor je maksimum između pozicija \(left\) i \(right\). Može se desiti da su oba elementa u jednom podsegmentu veći od oba elementa u drugom podsegmentu ili da je su dva najveća elementa dva maksimalna elementa u podsegmentima. Dakle, drugi maksimalni element je ili neodabrani maksimalni element ili drugi maksimalni element koji pripada istom segmentu kao i maksimalni element. Jednostavan način da odredimo oba elementa je: \[\begin{align*} m_1 &= \max \{ m_1^{left}, m_1^{right} \} \\ m_2 &= \min \{ \max \{ m_1^{left}, m_2^{right} \}, \max \{ m_2^{left}, m_1^{right} \} \} \end{align*}\] Kada smo formirali stablo, lako ćemo odrediti maksimalni proizvod u nekom segmentu. Slično je kao određivanje zbira elemenata u segmentu, pri čemu uvek određujemo maksimalnu i drugu maksimalnu vrednost u segmentu. Kada odredimo ova dva elementa, njihov proizvod je i maksimalni proizvod u traženom segmentu.
Složenost kreiranja segmentnog stabla je \(O(n \log n)\). Upiti ažuriranja stabla i određivanja maksimalnog i drugog maksimalnog elementa su složenosti \((O \log n)\). Imamo ukupno \(q\) takvih upita pa je ukupna složenost za obradu svih upita \(O(q \log n)\).
#include <iostream>
#include <vector>
#include <cmath>
#include <limits>
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], numeric_limits<int>::min() };
return;
}
const int mid = (start + end) / 2;
build(tree, arr, 2 * i + 1, start, mid);
build(tree, arr, 2 * i + 2, mid + 1, end);
const auto [m1_left, m2_left] = tree[2 * i + 1];
const auto [m1_right, m2_right] = tree[2 * i + 2];
tree[i] = {
max(m1_left, m1_right),
min(max(m1_left, m2_right), max(m2_left, m1_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 (l > end || r < start) {
return { numeric_limits<int>::min(), numeric_limits<int>::max() };
}
if (start >= l && end <= r) {
return tree[i];
}
int mid = (start + end) / 2;
const auto [m1_left, m2_left] = query(tree, 2 * i + 1, start, mid, l, r);
const auto [m1_right, m2_right] = query(tree, 2 * i + 2, mid + 1, end, l, r);
return {
max(m1_left, m1_right),
min(max(m1_left, m2_right), max(m2_left, m1_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, numeric_limits<int>::min() };
return;
}
const 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 [m1_left, m2_left] = tree[2 * i + 1];
const auto [m1_right, m2_right] = tree[2 * i + 2];
tree[i] = {
max(m1_left, m1_right),
min(max(m1_left, m2_right), max(m2_left, m1_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; cin >> n;
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);
int q; cin >> q;
while (q--) {
char c; cin >> c;
if (c == 'u') {
int i, v; cin >> i >> v;
update(tree, n, i, v);
} else {
int l, r; cin >> l >> r;
const auto [m1, m2] = query(tree, n, l, r);
cout << m1 * m2 << endl;
}
}
return 0;
}