Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- #define ll long long
- #define fi first
- #define si second
- using namespace std;
- const ll maxn = 200000;
- const ll inf = 1e18;
- ll n, m;
- ll a[maxn];
- ll t[maxn * 4];
- pair<ll, ll> nextt[4 * maxn];
- void prop(ll v) {
- if (nextt[v].si == 1) {
- nextt[v * 2] = nextt[v];
- nextt[v * 2 + 1] = nextt[v];
- } else {
- nextt[v * 2].fi += nextt[v].fi;
- nextt[v * 2 + 1].fi += nextt[v].fi;
- }
- if (nextt[v].si == 1) {
- t[v * 2] = nextt[v].fi;
- } else {
- t[v * 2] += nextt[v].fi;
- }
- if (nextt[v].si == 1) {
- t[v * 2 + 1] = nextt[v].fi;
- } else {
- t[v * 2 + 1] += nextt[v].fi;
- }
- nextt[v] = {0, 0};
- return;
- }
- ll newFunction(ll a, ll b) {
- return min(a, b);
- }
- void build(ll v, ll l, ll r) {
- if (l == r) {
- t[v] = a[l];
- return;
- }
- ll m = (r - l) / 2 + l;
- build(v * 2, l, m);
- build(v * 2 + 1, m + 1, r);
- t[v] = newFunction(t[v * 2], t[v * 2 + 1]);
- }
- void update(ll v, ll l, ll r, ll L, ll R, ll val, ll type) {
- if (R < l || L > r) {
- return;
- }
- prop(v);
- if (l == L && r == R) {
- if (type == 1) {
- t[v] = val;
- nextt[v] = {val, 1};
- }
- else {
- t[v] += val;
- nextt[v] = {val, 0};
- }
- return;
- }
- ll m = (r - l) / 2 + l;
- update(v * 2, l, m, L, min(m, R), val, type);
- update(v * 2 + 1, m + 1, r, max(L, m + 1), R, val, type);
- t[v] = newFunction(t[v * 2], t[v * 2 + 1]);
- }
- ll mint(ll v, ll l, ll r, ll lx, ll rx) {
- if (lx > r || rx < l) {
- return inf;
- }
- prop(v);
- if (lx == l && rx == r) {
- return t[v];
- }
- ll m = (r - l) / 2 + l;
- ll a = mint(v * 2, l, m, lx, min(m, rx));
- ll b = mint(v * 2 + 1, m + 1, r, max(lx, m + 1), rx);
- return newFunction(a, b);
- }
- int main() {
- ios::sync_with_stdio(0);
- cin.tie(0);
- cin >> n;
- for (ll i = 0; i < n; ++i) {
- cin >> a[i];
- }
- build(1, 0, n - 1);
- string s;
- while(cin >> s) {
- ll l, r, x;
- cin >> l >> r;
- if (s == "set") {
- cin >> x;
- update(1, 0, n - 1, l - 1, r - 1, x, 1);
- }
- if (s == "add") {
- cin >> x;
- update(1, 0, n - 1, l - 1, r - 1, x, 0);
- }
- if (s == "min") {
- cout << mint(1, 0, n - 1, l - 1, r - 1) <<"\n";
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement