Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- using namespace std;
- const long long N = 2 * 1e5 + 1;
- const long long MAXX = 1e18 + 1;
- long long a[N];
- long long x = 1;
- long long n;
- struct node
- {
- bool c = false;
- long long data;
- long long l, r;
- long long add;
- long long sett;
- node()
- {
- add = l = r = 0;
- data = MAXX;
- sett = MAXX;
- c = false;
- }
- };
- vector <node> t;
- void print()
- {
- for (long long i = 0; i < t.size(); ++i)
- {
- cout << t[i].c << " " << t[i].data << " " << t[i].l << " " << t[i].r << '\n';
- }
- }
- void push(long long v)
- {
- if ((t[v].l != t[v].r) && t[2 * v + 2].c)
- {
- if (t[v].sett != MAXX)
- {
- t[2 * v + 2].sett = t[v].sett;
- t[2 * v + 2].data = t[v].sett;
- t[2 * v + 2].add = 0;
- }
- if (t[v].add != 0)
- {
- if (t[2 * v + 2].sett != MAXX)
- {
- t[2 * v + 2].sett += t[v].add;
- }
- else
- {
- t[2 * v + 2].add += t[v].add;
- }
- t[2 * v + 2].data += t[v].add;
- }
- }
- if ((t[v].l != t[v].r) && t[2 * v + 1].c)
- {
- if (t[v].sett != MAXX)
- {
- t[2 * v + 1].sett = t[v].sett;
- t[2 * v + 1].data = t[v].sett;
- t[2 * v + 1].add = 0;
- }
- if (t[v].add != 0)
- {
- if (t[2 * v + 1].sett < MAXX)
- {
- t[2 * v + 1].sett += t[v].add;
- }
- else
- {
- t[2 * v + 1].add += t[v].add;
- }
- t[2 * v + 1].data += t[v].add;
- }
- }
- t[v].sett = MAXX;
- t[v].add = 0;
- }
- long long query(long long v, long long a, long long b)
- {
- push(v);
- if ((t[v].r < a) || (t[v].l > b))
- {
- return MAXX;
- }
- if ((t[v].l >= a) && (t[v].r <= b))
- {
- return t[v].data;
- }
- long long ans = min(query(2 * v + 1, a, b), query(2 * v + 2, a, b));
- t[v].data = min(t[2 * v + 1].data, t[2 * v + 2].data);
- return ans;
- }
- void update_add(long long v, long long a, long long b, long long val)
- {
- push(v);
- if ((t[v].r < a) || (t[v].l > b))
- {
- return;
- }
- if ((t[v].l >= a) && (t[v].r <= b))
- {
- if (t[v].sett != MAXX)
- {
- t[v].sett += val;
- }
- else
- {
- t[v].add += val;
- }
- t[v].data += val;
- push(v);
- return;
- }
- //push(v);
- update_add(2 * v + 1, a, b, val);
- update_add(2 * v + 2, a, b, val);
- t[v].data = min(t[2 * v + 1].data, t[2 * v + 2].data);
- }
- void update_sett(long long v, long long a, long long b, long long val)
- {
- push(v);
- if ((t[v].r < a) || (t[v].l > b))
- {
- return;
- }
- push(v);
- if ((t[v].l >= a) && (t[v].r <= b))
- {
- t[v].sett = val;
- t[v].data = t[v].sett;
- t[v].add = 0;
- push(v);
- return;
- }
- //push(v);
- update_sett(2 * v + 1, a, b, val);
- update_sett(2 * v + 2, a, b, val);
- t[v].data = min(t[2 * v + 1].data, t[2 * v + 2].data);
- }
- void build(long long v, long long l, long long r)
- {
- t[v].add = 0;
- t[v].sett = MAXX;
- t[v].l = l;
- t[v].r = r;
- t[v].c = true;
- if (l == r)
- {
- t[v].data = a[l];
- }
- else
- {
- long long m = (l + r) / 2;
- build(2 * v + 1, l, m);
- build(2 * v + 2, m + 1, r);
- t[v].data = min(t[2 * v + 1].data, t[2 * v + 2].data);
- }
- }
- int main()
- {
- freopen("rmq2.in", "r", stdin);
- freopen("rmq2.out", "w", stdout);
- ios_base::sync_with_stdio(false);
- cin.tie(nullptr);
- cin >> n;
- for (int i = 0; i < n; ++i) {
- cin >> a[i];
- }
- t.resize(static_cast<unsigned long>(4 * n));
- build(0, 0, n - 1);
- string s;
- //print();
- //cout << '\n';
- while (cin >> s)
- {
- if (s == "min")
- {
- long long tl, tr;
- cin >> tl >> tr;
- --tl;
- --tr;
- cout << query(0, tl, tr) << '\n';
- }
- else if (s == "add")
- {
- long long tl, tr, val;
- cin >> tl >> tr >> val;
- --tl;
- --tr;
- update_add(0, tl, tr, val);
- }
- else if (s == "set")
- {
- long long tl, tr, val;
- cin >> tl >> tr >> val;
- --tl;
- --tr;
- update_sett(0, tl, tr, val);
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement