Submit Info #15656

Problem Lang User Status Time Memory
Range Chmin Chmax Add Range Sum cpp BlueDiamond AC 380 ms 23.67 MiB

ケース詳細
Name Status Time Memory
example_00 AC 6 ms 6.80 MiB
max_random_00 AC 369 ms 23.67 MiB
max_random_01 AC 373 ms 23.66 MiB
max_random_02 AC 380 ms 23.67 MiB
medium_00 AC 7 ms 6.92 MiB
medium_01 AC 10 ms 6.83 MiB
medium_02 AC 9 ms 6.82 MiB
random_00 AC 250 ms 15.49 MiB
random_01 AC 277 ms 23.46 MiB
random_02 AC 158 ms 11.30 MiB
small_00 AC 5 ms 6.81 MiB
small_01 AC 7 ms 6.80 MiB
small_02 AC 4 ms 6.80 MiB
small_03 AC 0 ms 6.79 MiB
small_04 AC 7 ms 6.84 MiB
small_05 AC 6 ms 6.80 MiB
small_06 AC 10 ms 6.80 MiB
small_07 AC 6 ms 6.80 MiB
small_08 AC 5 ms 6.80 MiB
small_09 AC 5 ms 6.80 MiB

#include <bits/stdc++.h> using namespace std; void fastio() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); } typedef long long ll; const int N = (int) 2e5 + 7; int n; int q; ll mn[4 * N]; ll mx[4 * N]; ll sum[4 * N]; ll a[4 * N]; ll b[4 * N]; void push(int v, int tl, int tr) { if (a[v] == 1 && b[v] == 0) { return; } mn[v] = mn[v] * a[v] + b[v]; mx[v] = mx[v] * a[v] + b[v]; sum[v] = sum[v] * a[v] + (ll) (tr - tl + 1) * b[v]; if (tl < tr) { a[2 * v] = a[2 * v] * a[v]; b[2 * v] = b[2 * v] * a[v] + b[v]; a[2 * v + 1] = a[2 * v + 1] * a[v]; b[2 * v + 1] = b[2 * v + 1] * a[v] + b[v]; } a[v] = 1; b[v] = 0; } void minop(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 && x <= mn[v]) { a[v] = 0; b[v] = x; push(v, tl, tr); return; } int tm = (tl + tr) / 2; minop(2 * v, tl, tm, l, r, x); minop(2 * v + 1, tm + 1, tr, l, r, x); sum[v] = sum[2 * v] + sum[2 * v + 1]; mn[v] = min(mn[2 * v], mn[2 * v + 1]); mx[v] = max(mx[2 * v], mx[2 * v + 1]); } void maxop(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 && x >= mx[v]) { a[v] = 0; b[v] = x; push(v, tl, tr); return; } int tm = (tl + tr) / 2; maxop(2 * v, tl, tm, l, r, x); maxop(2 * v + 1, tm + 1, tr, l, r, x); sum[v] = sum[2 * v] + sum[2 * v + 1]; mn[v] = min(mn[2 * v], mn[2 * v + 1]); mx[v] = max(mx[2 * v], mx[2 * v + 1]); } void add(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) { b[v] += x; push(v, tl, tr); return; } int tm = (tl + tr) / 2; add(2 * v, tl, tm, l, r, x); add(2 * v + 1, tm + 1, tr, l, r, x); sum[v] = sum[2 * v] + sum[2 * v + 1]; mn[v] = min(mn[2 * v], mn[2 * v + 1]); mx[v] = max(mx[2 * v], mx[2 * v + 1]); } 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 minop(int l, int r, ll x) { minop(1, 1, n, l, r, x); } void maxop(int l, int r, ll x) { maxop(1, 1, n, l, r, x); } void add(int l, int r, ll x) { add(1, 1, n, l, r, x); } ll get(int l, int r) { return get(1, 1, n, l, r); } int main() { fastio(); cin >> n >> q; for (int i = 0; i < 4 * N; i++) { a[i] = 1; } for (int i = 1; i <= n; i++) { ll x; cin >> x; add(i, i, x); } for (int i = 1; i <= q; i++) { int t, l, r; cin >> t >> l >> r; l++; if (t == 0) { ll x; cin >> x; minop(l, r, x); } if (t == 1) { ll x; cin >> x; maxop(l, r, x); } if (t == 2) { ll x; cin >> x; add(l, r, x); } if (t == 3) { cout << get(l, r) << "\n"; } } return 0; }