Mai intai trebuie sa te autentifici.

Cod sursa(job #2883503)

Utilizator MocalinnoMoca Andrei Catalin Mocalinno 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;
}