Mai intai trebuie sa te autentifici.
Cod sursa(job #2883503)
Utilizator | Data | 1 aprilie 2022 16:06:55 | |
---|---|---|---|
Problema | Infasuratoare convexa | Scor | 0 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 2.73 kb |
#include <bits/stdc++.h>
using namespace std;
#define int int64_t
int const Inf(1e18);
vector<int> a;
class SegTree {
public:
SegTree(int const& _n) : n(_n) {
Min = vector<int>(4 * n, Inf);
flag = vector<int>(4 * n);
Build(1, 1, n);
}
inline void Update(int const& _L, int const& _R, int const& v) {
L = _L, R = _R;
Update(1, 1, n, v);
}
inline int Query(int const& _L, int const& _R) {
L = _L, R = _R;
return Query(1, 1, n);
}
private:
inline void UpdateNode(int const& node, int const& val) {
flag[node] += val;
}
inline void Update(int const& node, int const& st, int const& dr, int const& val)
{
if (L <= st && dr <= R) {
UpdateNode(node, val);
PushDown(node, st, dr);
return;
}
PushDown(node, st, dr);
int mid = (st + dr) / 2;
if (L <= mid)
Update(2 * node, st, mid, val);
if (mid < R)
Update(2 * node + 1, mid + 1, dr, val);
if (st != dr)
Min[node] = min(Min[2 * node], Min[2 * node + 1]);
}
inline int Query(int const& node, int const& st, int const& dr) {
PushDown(node, st, dr);
if (L <= st && dr <= R)
return Min[node];
int mid = (st + dr) / 2, q1 = Inf, q2 = Inf;
if (L <= mid)
q1 = Query(2 * node, st, mid);
if (mid < R)
q2 = Query(2 * node + 1, mid + 1, dr);
return min(q1, q2);
}
inline void PushDown(int const& node, int const& st, int const& dr) {
if (st < dr && flag[node] != 0) {
UpdateNode(2 * node, flag[node]);
UpdateNode(2 * node + 1, flag[node]);
flag[node] = 0;
}
}
inline void Build(int const& node, int const& st, int const& dr) {
if (st == dr) {
Min[node] = a[st];
return;
}
int mid = (st + dr) / 2;
Build(2 * node, st, mid);
Build(2 * node + 1, mid + 1, dr);
Min[node] = min(Min[2 * node], Min[2 * node + 1]);
}
int n, L, R;
vector<int> flag, Min;
};
int n, q;
string const& task("aimi");
ifstream fin(task + ".in");
ofstream fout(task + ".out");
main() {
fin >> n;
a.resize(n + 1);
for (int i = 1; i <= n; ++i)
fin >> a[i];
fin >> q;
SegTree aint(n);
while (q--) {
int op, x, y;
fin >> op >> x >> y;
if (op == 1)
fout << aint.Query(x, y) << '\n';
else {
int val;
fin >> val;
aint.Update(x, y, val);
}
}
return 0;
}