Submit Info #50992

Problem Lang User Status Time Memory
Range Chmin Chmax Add Range Sum cpp blackking26 AC 521 ms 31.21 MiB

ケース詳細
Name Status Time Memory
example_00 AC 1 ms 0.61 MiB
max_random_00 AC 377 ms 31.09 MiB
max_random_01 AC 381 ms 31.09 MiB
max_random_02 AC 373 ms 31.09 MiB
medium_00 AC 2 ms 0.84 MiB
medium_01 AC 1 ms 0.71 MiB
medium_02 AC 2 ms 0.71 MiB
random2_00 AC 460 ms 31.20 MiB
random2_01 AC 456 ms 31.21 MiB
random2_02 AC 460 ms 31.21 MiB
random3_00 AC 521 ms 30.21 MiB
random3_01 AC 519 ms 30.21 MiB
random3_02 AC 521 ms 30.21 MiB
random_00 AC 249 ms 16.33 MiB
random_01 AC 272 ms 30.46 MiB
random_02 AC 173 ms 8.59 MiB
small_00 AC 1 ms 0.70 MiB
small_01 AC 1 ms 0.71 MiB
small_02 AC 1 ms 0.72 MiB
small_03 AC 1 ms 0.71 MiB
small_04 AC 1 ms 0.71 MiB
small_05 AC 1 ms 0.71 MiB
small_06 AC 1 ms 0.71 MiB
small_07 AC 1 ms 0.71 MiB
small_08 AC 1 ms 0.61 MiB
small_09 AC 1 ms 0.71 MiB

#include <iostream> #include <vector> #include <algorithm> #include <tuple> #define pii pair<int, int> #define ff first #define ss second using namespace std; const long long INF = (long long)5e17 + 100; long long A[202020]; struct Node { long long sum, lazy; long long mx, smx, mn, smn; int mxcnt, mncnt; }seg[808080]; void mrge(int ind) { Node &nd = seg[ind], &x = seg[ind << 1], &y = seg[ind << 1 | 1]; nd.sum = x.sum + y.sum; if(x.mx == y.mx) nd.mx = x.mx, nd.mxcnt = x.mxcnt + y.mxcnt, nd.smx = max(x.smx, y.smx); else if(x.mx > y.mx) nd.mx = x.mx, nd.mxcnt = x.mxcnt, nd.smx = max(x.smx, y.mx); else nd.mx = y.mx, nd.mxcnt = y.mxcnt, nd.smx = max(x.mx, y.smx); if(x.mn == y.mn) nd.mn = x.mn, nd.mncnt = x.mncnt + y.mncnt, nd.smn = min(x.smn, y.smn); else if(x.mn < y.mn) nd.mn = x.mn, nd.mncnt = x.mncnt, nd.smn = min(x.smn, y.mn); else nd.mn = y.mn, nd.mncnt = y.mncnt, nd.smn = min(x.mn, y.smn); } void prop(int ind, int s, int e) { int mid = s + e >> 1; for(auto x : {ind << 1, ind << 1 | 1}) { int cnt; if(x == ind * 2) cnt = mid - s; else cnt = e - mid; seg[x].sum += seg[ind].lazy * cnt; seg[x].lazy += seg[ind].lazy; seg[x].mx += seg[ind].lazy; seg[x].mn += seg[ind].lazy; if(seg[x].smx != -INF) seg[x].smx += seg[ind].lazy; if(seg[x].smn != INF) seg[x].smn += seg[ind].lazy; if(seg[x].mx > seg[ind].mx) { seg[x].sum -= seg[x].mxcnt * (seg[x].mx - seg[ind].mx); if(seg[x].mx == seg[x].mn) seg[x].mx = seg[x].mn = seg[ind].mx; else if(seg[x].mx == seg[x].smn) seg[x].mx = seg[x].smn = seg[ind].mx; else seg[x].mx = seg[ind].mx; } if(seg[x].mn < seg[ind].mn) { seg[x].sum += seg[x].mncnt * (seg[ind].mn - seg[x].mn); if(seg[x].mx == seg[x].mn) seg[x].mx = seg[x].mn = seg[ind].mn; else if(seg[x].smx == seg[x].mn) seg[x].smx = seg[x].mn = seg[ind].mn; else seg[x].mn = seg[ind].mn; } } seg[ind].lazy = 0; } void init(int ind, int s, int e) { if(s + 1 == e) { seg[ind].sum = seg[ind].mn = seg[ind].mx = A[s]; seg[ind].smx = -INF; seg[ind].smn = INF; seg[ind].lazy = 0; seg[ind].mxcnt = seg[ind].mncnt = 1; return; } int mid = s + e >> 1; init(ind << 1, s, mid); init(ind << 1 | 1, mid, e); mrge(ind); } void xupd(int ind, int s, int e, int l, int r, long long x) { if(e <= l || r <= s || seg[ind].mn >= x) return; if(l <= s && e <= r && seg[ind].smn > x) { seg[ind].sum += (x - seg[ind].mn) * seg[ind].mncnt; if(seg[ind].mx == seg[ind].mn) seg[ind].mx = seg[ind].mn = x; else if(seg[ind].smx == seg[ind].mn) seg[ind].smx = seg[ind].mn = x; else seg[ind].mn = x; return; } prop(ind, s, e); int mid = s + e >> 1; xupd(ind << 1, s, mid, l, r, x); xupd(ind << 1 | 1, mid, e, l, r, x); mrge(ind); } void nupd(int ind, int s, int e, int l, int r, long long x) { if(e <= l || r <= s || seg[ind].mx <= x) return; if(l <= s && e <= r && seg[ind].smx < x) { seg[ind].sum -= (seg[ind].mx - x) * seg[ind].mxcnt; if(seg[ind].mx == seg[ind].mn) seg[ind].mx = seg[ind].mn = x; else if(seg[ind].smn == seg[ind].mx) seg[ind].smn = seg[ind].mx = x; else seg[ind].mx = x; return; } prop(ind, s, e); int mid = s + e >> 1; nupd(ind << 1, s, mid, l, r, x); nupd(ind << 1 | 1, mid, e, l, r, x); mrge(ind); } void supd(int ind, int s, int e, int l, int r, long long x) { if(e <= l || r <= s) return; if(l <= s && e <= r) { seg[ind].sum += x * (e - s); seg[ind].lazy += x; seg[ind].mx += x; seg[ind].mn += x; if(seg[ind].smx != -INF) seg[ind].smx += x; if(seg[ind].smn != INF) seg[ind].smn += x; return; } prop(ind, s, e); int mid = s + e >> 1; supd(ind << 1, s, mid, l, r, x); supd(ind << 1 | 1, mid, e, l, r, x); mrge(ind); } long long qry(int ind, int s, int e, int l, int r) { if(e <= l || r <= s) return 0; if(l <= s && e <= r) return seg[ind].sum; prop(ind, s, e); int mid = s + e >> 1; return qry(ind << 1, s, mid, l, r) + qry(ind << 1 | 1, mid, e, l, r); } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); // freopen("in.txt", "r", stdin); int n, T; cin >> n >> T; for(int i = 0; i < n; ++i) cin >> A[i]; init(1, 0, n); while(T--) { int c; cin >> c; if(c == 0) { int l, r; long long x; cin >> l >> r >> x; nupd(1, 0, n, l, r, x); } else if(c == 1) { int l, r; long long x; cin >> l >> r >> x; xupd(1, 0, n, l, r, x); } else if(c == 2) { int l, r; long long x; cin >> l >> r >> x; supd(1, 0, n, l, r, x); } else { int l, r; cin >> l >> r; cout << qry(1, 0, n, l, r) << '\n'; } } }