Neka je dat niz funkcija \(f_0, f_1, \ldots, f_{n-1}\), gde je \(i\)-ta funkcija oblika \(f_i(x) = a_i x + b_i\) (funkcije su linearne po \(x\)). Treba implementirati efikasnu promenu koeficijenata određene funkcije, kao i kompoziciju više uzastopnih funkcija.
Sa standardnog ulaza unose se dva cela broja \(n\) i \(q\) iz intervala \([1, 100000]\). Prvo se unosi \(n\) linearnih funkcija preko para svojih koeficijenata, svaka u novom redu, a zatim i \(q\) upita oblika:
Za svaki upit tipa \(1\) na standardni izlaz ispisati vrednost odgovarajuće kompozicije.
5 5 1 2 3 4 5 6 7 8 9 10 1 0 4 11 1 2 4 12 0 1 13 14 1 0 4 15 1 2 4 16
14005 4240 74485 5500
Ideja rešenja je da od niza funkcija napravimo segmentno stablo, što nam omogućava da na oba upita odgovorimo u vremenu \(O(\log n)\). U čvorovima segmentnog stabla čuvaćemo kompoziciju segmenta funkcija pokrivenu tim čvorom. Ako neki čvor pokriva segment \([l, r]\), onda će se u čvoru čuvati \(f_r \circ f_{r-1} \circ \ldots \circ f_l\). Bitno je napomenuti da u čvorovima čuvamo uređeni par u kome je prvi element koeficijent uz \(x\), a drugi element slobodni član, tj. par \((a, b)\) odgovara funkciji \(f(x) = ax + b\).
Ako pretpostavimo da se u korenu levog podstabla nalazi funkcija \(f(x) = a x + d\), a u korenu desnog podstabla funckija \(g(x) = cx + d\), tada se u korenu stabla mora nalaziti funkcija \[\begin{align*} g(f(x)) &= c (ax + b) + d \\ &= (ca) x + (c b + d). \\ \end{align*}\] Dakle, ukoliko su funkcije korena levog, odnosno korena desnog, podstabla redom \(f(x)\) i \(g(x)\) predstavljene parovima \((a, b)\) i \((c, d)\), tada se u korenu stabla mora nalaziti \((c a, c b + d)\). Neutral za kompoziciju funkcija je funkcija \(id(x) = x = 1x + 0\), te je njen odgovarajući par \((1,0)\). Sada je implementacija algoritma jednostavna.
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <limits>
#include <cmath>
using namespace std;
void build(vector<pair<int, int>> &tree, const vector<pair<int, int>> &arr,
const int i, const int start, const int end)
{
if (start == end) {
tree[i] = arr[start];
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 [a, b] = tree[2 * i + 1]; // f(x) = a * x + b
const auto [c, d] = tree[2 * i + 2]; // g(x) = c * x + d
tree[i] = { c * a, c * b + d }; // g(f(x)) = c * (a * x + b) + d
// = (c * a) * x + (c * b + d)
}
void build(vector<pair<int, int>> &tree, const int n,
const vector<pair<int, int>> &arr)
{
build(tree, arr, 0, 0, n - 1);
}
pair<int, int> query(const vector<pair<int, int>> &tree, int i, int start, int end, int l, int r)
{
if (r < start || l > end) {
return { 1, 0 };
}
if (l <= start && r >= end) {
return tree[i];
}
const int mid = (start + end) / 2;
const auto [a, b] = query(tree, 2 * i + 1, start, mid, l, r);
const auto [c, d] = query(tree, 2 * i + 2, mid + 1, end, l, r);
return { c * a, c * b + d };
}
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 e, const int f)
{
if (start == end) {
tree[i] = { e, f };
return;
}
const int mid = (start + end) / 2;
if (ind <= mid) {
update(tree, 2 * i + 1, start, mid, ind, e, f);
} else {
update(tree, 2 * i + 2, mid + 1, end, ind, e, f);
}
const auto [a, b] = tree[2 * i + 1]; // f(x) = a * x + b
const auto [c, d] = tree[2 * i + 2]; // g(x) = c * x + d
tree[i] = { c * a, c * b + d }; // g(f(x)) = c * (a * x + b) + d
// = (c * a) * x + (c * b + d)
}
void update(vector<pair<int, int>> &tree, const int n,
const int i, const int c, const int d)
{
update(tree, 0, 0, n - 1, i, c, d);
}
int main(void)
{
int n, q;
cin >> n >> q;
vector<pair<int, int>> arr(n);
for (int i = 0; i < n; i++) {
cin >> arr[i].first >> arr[i].second;
}
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--) {
int op; cin >> op;
if (op == 0) {
int i, c, d; cin >> i >> c >> d;
update(tree, n, i, c, d);
} else if (op == 1) {
int l, r, x; cin >> l >> r >> x;
const auto [a, b] = query(tree, n, l, r);
cout << a * x + b << endl;
}
}
return 0;
}