Solução de Frederico Bulhões
Para esse problema vamos usar uma estrutura chamada de segment tree. Com ele podemos consultar mínimo e máximo em um intervalo qualquer e também podemos fazer updates um uma posição.
Para responder cada query vamos fazer a consulta da máximo naquele intervalo e subtrair pela consulta de mínimo daquele intervalo. O mudança de preço é simplismente um update normal em uma segment tree.
Caso queira aprender melhor a estrutura da segment tree pode consutar a aula do Codcad de segment tree.
Código para melhor entendimento:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| // solucao de Frederico Bulhoes | |
| #include <bits/stdc++.h> | |
| #define LEFT ((no<<1)+1) | |
| #define RIGHT ((no<<1)+2) | |
| using namespace std; | |
| const int maxn = 100010; | |
| struct node | |
| { | |
| int min, max; | |
| }; | |
| node operator&(const node &l, const node &r) | |
| { | |
| return {min(l.min, r.min), | |
| max(l.max, r.max)}; | |
| } | |
| int v[maxn]; | |
| node tree[maxn*4]; | |
| void build(int no, int l, int r) | |
| { | |
| if (l == r) { | |
| tree[no] = {v[l], v[l]}; | |
| return; | |
| } | |
| int m = (l+r)>>1; | |
| build(LEFT, l, m); | |
| build(RIGHT, m+1, r); | |
| tree[no] = tree[LEFT] & tree[RIGHT]; | |
| } | |
| void upd(int no, int l, int r, int p, int val) | |
| { | |
| if (l == r) { | |
| tree[no] = {val, val}; | |
| return; | |
| } | |
| int m = (l+r)>>1; | |
| if (p <= m) upd(LEFT, l, m, p, val); | |
| else upd(RIGHT, m+1, r, p, val); | |
| tree[no] = tree[LEFT] & tree[RIGHT]; | |
| } | |
| node get(int no, int l, int r, int a, int b) | |
| { | |
| if (a <= l and r <= b) return tree[no]; | |
| int m = (l+r)>>1; | |
| if (b <= m) return get(LEFT, l, m, a, b); | |
| if (a > m) return get(RIGHT, m+1, r, a, b); | |
| return get(LEFT, l, m, a, b) & get(RIGHT, m+1, r, a, b); | |
| } | |
| int main() | |
| { | |
| ios_base::sync_with_stdio(false); | |
| cin.tie(0); | |
| int n; | |
| while (cin >> n) { | |
| for (int i = 1; i <= n; i++) cin >> v[i]; | |
| build(0, 1, n); | |
| int q; | |
| cin >> q; | |
| while (q--) { | |
| int op; | |
| cin >> op; | |
| if (op == 1) { | |
| int p, val; | |
| cin >> p >> val; | |
| upd(0, 1, n, p, val); | |
| } | |
| else { | |
| int l, r; | |
| cin >> l >> r; | |
| node ans = get(0, 1, n, l, r); | |
| cout << ans.max-ans.min << "\n"; | |
| } | |
| } | |
| } | |
| } |