Submit Info #17778

Problem Lang User Status Time Memory
Range Chmin Chmax Add Range Sum cpp mihnea AC 1915 ms 38.17 MiB

ケース詳細
Name Status Time Memory
example_00 AC 2 ms 0.67 MiB
max_random_00 AC 1909 ms 38.17 MiB
max_random_01 AC 1915 ms 38.12 MiB
max_random_02 AC 1902 ms 38.15 MiB
medium_00 AC 6 ms 0.86 MiB
medium_01 AC 6 ms 0.72 MiB
medium_02 AC 6 ms 0.80 MiB
random_00 AC 1229 ms 19.67 MiB
random_01 AC 1373 ms 37.98 MiB
random_02 AC 729 ms 10.37 MiB
small_00 AC 2 ms 0.73 MiB
small_01 AC 1 ms 0.67 MiB
small_02 AC 1 ms 0.67 MiB
small_03 AC 1 ms 0.78 MiB
small_04 AC 2 ms 0.67 MiB
small_05 AC 1 ms 0.67 MiB
small_06 AC 1 ms 0.66 MiB
small_07 AC 1 ms 0.77 MiB
small_08 AC 2 ms 0.67 MiB
small_09 AC 1 ms 0.67 MiB

#include <bits/stdc++.h> using namespace std; typedef long long ll; const ll INF = (ll) 1e18; const int N = (int) 2e5 + 7; int n, q; ll addmx[4 * N]; ll addmn[4 * N]; ll addall[4 * N]; ll mn[4 * N]; ll mx[4 * N]; int cmn[4 * N]; int cmx[4 * N]; ll mn2[4 * N]; ll mx2[4 * N]; ll sum[4 * N]; bool eq[4 * N]; ll getmn(int v) { if (eq[v]) { addall[v] += addmn[v]; addall[v] += addmx[v]; addmn[v] = addmx[v] = 0; } return mn[v] + addall[v] + addmn[v]; } ll getmx(int v) { if (eq[v]) { addall[v] += addmn[v]; addall[v] += addmx[v]; addmn[v] = addmx[v] = 0; } return mx[v] + addall[v] + addmx[v]; } void push(int v, int tl, int tr) { bool rel1 = (mn[v] == mx2[v]); bool rel2 = (mn2[v] == mx[v]); if (eq[v]) { addall[v] += addmn[v]; addall[v] += addmx[v]; addmn[v] = addmx[v] = 0; } if (addall[v]) { mn[v] += addall[v]; mx[v] += addall[v]; mn2[v] += addall[v]; mx2[v] += addall[v]; sum[v] += addall[v] * (tr - tl + 1); if (tl < tr) { addall[2 * v] += addall[v]; addall[2 * v + 1] += addall[v]; } addall[v] = 0; } if (addmn[v]) { mn[v] += addmn[v]; sum[v] += addmn[v] * cmn[v]; if (tl < tr) { ll val = min(getmn(2 * v), getmn(2 * v + 1)); if (getmn(2 * v) == val) { addmn[2 * v] += addmn[v]; } if (getmn(2 * v + 1) == val) { addmn[2 * v + 1] += addmn[v]; } } addmn[v] = 0; } if (addmx[v]) { mx[v] += addmx[v]; sum[v] += addmx[v] * cmx[v]; if (tl < tr) { ll val = max(getmx(2 * v), getmx(2 * v + 1)); if (getmx(2 * v) == val) { addmx[2 * v] += addmx[v]; } if (getmx(2 * v + 1) == val) { addmx[2 * v + 1] += addmx[v]; } } addmx[v] = 0; } if (rel1) { mx2[v] = mn[v]; } if (rel2) { mn2[v] = mx[v]; } } ll second_max(vector<ll> a) { ll mx = -INF, mx2 = -INF; for (auto &x : a) { mx = max(mx, x); } for (auto &x : a) { if (x < mx) { mx2 = max(mx2, x); } } return mx2; } ll second_min(vector<ll> a) { ll mn = INF, mn2 = INF; for (auto &x : a) { mn = min(mn, x); } for (auto &x : a) { if (x > mn) { mn2 = min(mn2, x); } } return mn2; } void join(int v) { mn[v] = min(mn[2 * v], mn[2 * v + 1]); mx[v] = max(mx[2 * v], mx[2 * v + 1]); cmn[v] = cmn[2 * v] * (mn[2 * v] == mn[v]) + cmn[2 * v + 1] * (mn[2 * v + 1] == mn[v]); cmx[v] = cmx[2 * v] * (mx[2 * v] == mx[v]) + cmx[2 * v + 1] * (mx[2 * v + 1] == mx[v]); sum[v] = sum[2 * v] + sum[2 * v + 1]; if (mn[v] == mx[v]) { eq[v] = 1; } else { eq[v] = 0; vector<ll> a, b; for (int v2 = 2 * v; v2 <= 2 * v + 1; v2++) { if (eq[v2]) { a.push_back(mn[v2]); b.push_back(mx[v2]); } else { a.push_back(mn[v2]); a.push_back(mn2[v2]); b.push_back(mx[v2]); b.push_back(mx2[v2]); } } mn2[v] = second_min(a); mx2[v] = second_max(b); } } void mnop(int v, int tl, int tr, int l, int r, ll x) { push(v, tl, tr); if (tr < l || r < tl || mx[v] <= x) { return; } if (l <= tl && tr <= r && (eq[v] || mx2[v] < x)) { addmx[v] = x - mx[v]; push(v, tl, tr); return; } int tm = (tl + tr) / 2; mnop(2 * v, tl, tm, l, r, x); mnop(2 * v + 1, tm + 1, tr, l, r, x); join(v); } void mxop(int v, int tl, int tr, int l, int r, ll x) { push(v, tl, tr); if (tr < l || r < tl || mn[v] >= x) { return; } if (l <= tl && tr <= r && (eq[v] || mn2[v] > x)) { addmn[v] = x - mn[v]; push(v, tl, tr); return; } int tm = (tl + tr) / 2; mxop(2 * v, tl, tm, l, r, x); mxop(2 * v + 1, tm + 1, tr, l, r, x); join(v); } ll get(int v, int tl, int tr, int l, int r) { push(v, tl, tr); if (tr < l || r < tl) { return 0LL; } if (l <= tl && tr <= r) { return sum[v]; } int tm = (tl + tr) / 2; return get(2 * v, tl, tm, l, r) + get(2 * v + 1, tm + 1, tr, l, r); } void addop(int v, int tl, int tr, int l, int r, ll x) { push(v, tl, tr); if (tr < l || r < tl) { return; } if (l <= tl && tr <= r) { addall[v] = x; push(v, tl, tr); return; } int tm = (tl + tr) / 2; addop(2 * v, tl, tm, l, r, x); addop(2 * v + 1, tm + 1, tr, l, r, x); join(v); } void mnop(int l, int r, ll x) { mnop(1, 1, n, l, r, x); } void mxop(int l, int r, ll x) { mxop(1, 1, n, l, r, x); } void addop(int l, int r, ll x) { addop(1, 1, n, l, r, x); } ll get(int l, int r) { return get(1, 1, n, l, r); } void build(int v, int tl, int tr) { if (tl == tr) { cmn[v] = cmx[v] = eq[v] = 1; return; } int tm = (tl + tr) / 2; build(2 * v, tl, tm); build(2 * v + 1, tm + 1, tr); join(v); } void build() { build(1, 1, n); } int main() { ios::sync_with_stdio(0); cin.tie(0); cin >> n >> q; build(); for (int i = 1; i <= n; i++) { ll x; cin >> x; addop(i, i, x); } for (int it = 1; it <= q; it++) { int tp, l, r; cin >> tp >> l >> r; l++; if (tp == 0) { ll x; cin >> x; mnop(l, r, x); } if (tp == 1) { ll x; cin >> x; mxop(l, r, x); } if (tp == 2) { ll x; cin >> x; addop(l, r, x); } if (tp == 3) { cout << get(l, r) << "\n"; } } return 0; }