Submit Info #13740

Problem Lang User Status Time Memory
Range Chmin Chmax Add Range Sum cpp PinkRabbit AC 470 ms 39.42 MiB

ケース詳細
Name Status Time Memory
example_00 AC 1 ms 0.42 MiB
max_random_00 AC 453 ms 39.42 MiB
max_random_01 AC 470 ms 39.42 MiB
max_random_02 AC 466 ms 39.42 MiB
medium_00 AC 2 ms 0.68 MiB
medium_01 AC 2 ms 0.42 MiB
medium_02 AC 3 ms 0.67 MiB
random_00 AC 296 ms 20.30 MiB
random_01 AC 333 ms 39.19 MiB
random_02 AC 202 ms 10.54 MiB
small_00 AC 1 ms 0.60 MiB
small_01 AC 0 ms 0.68 MiB
small_02 AC 1 ms 0.68 MiB
small_03 AC 1 ms 0.67 MiB
small_04 AC 3 ms 0.68 MiB
small_05 AC 1 ms 0.61 MiB
small_06 AC 1 ms 0.68 MiB
small_07 AC 2 ms 0.67 MiB
small_08 AC 0 ms 0.67 MiB
small_09 AC 1 ms 0.72 MiB

#include <cstdio> #include <algorithm> typedef long long LL; const LL Inf = 0x3f3f3f3f3f3f3f3f; const int MN = 200005, MS = 1 << 19 | 7; int N, Q; #define li (i << 1) #define ri (li | 1) #define mid ((l + r) >> 1) #define ls li, l, mid #define rs ri, mid + 1, r struct dat { LL sum; LL mx1, mx2, mn1, mn2; int mxc, mnc; // char *Print() { // char s[99]; // sprintf(s, "(%lld, (%lld, %lld, %d), (%lld, %lld, %d))", sum, mx1, mx2, mxc, mn1, mn2, mnc); // return s; // } dat() {} friend dat operator + (dat a, dat b) { // printf("%s + %s\n", a.Print(), b.Print()); a.sum += b.sum; if (a.mx1 < b.mx1) { a.mx2 = std::max(a.mx1, b.mx2); a.mx1 = b.mx1, a.mxc = b.mxc; } else if (a.mx1 == b.mx1) { a.mxc += b.mxc; a.mx2 = std::max(a.mx2, b.mx2); } else a.mx2 = std::max(a.mx2, b.mx1); if (a.mn1 > b.mn1) { a.mn2 = std::min(a.mn1, b.mn2); a.mn1 = b.mn1, a.mnc = b.mnc; } else if (a.mn1 == b.mn1) { a.mnc += b.mnc; a.mn2 = std::min(a.mn2, b.mn2); } else a.mn2 = std::min(a.mn2, b.mn1); return a; } } tr[MS]; int len[MS]; LL tlb[MS], tub[MS], tbi[MS]; inline void P(int i, LL lb, LL ub, LL bi) { if (tr[i].mx1 == tr[i].mn1) { if (tr[i].mx1 < lb) tr[i].mx1 = tr[i].mn1 = lb, tr[i].sum = lb * len[i]; if (ub < tr[i].mn1) tr[i].mx1 = tr[i].mn1 = ub, tr[i].sum = ub * len[i]; } else if (tr[i].mx1 == tr[i].mn2) { if (ub < tr[i].mx1) tr[i].sum -= (tr[i].mx1 - ub) * tr[i].mxc, tr[i].mx1 = tr[i].mn2 = ub; if (tr[i].mn1 < lb) tr[i].sum += (lb - tr[i].mn1) * tr[i].mnc, tr[i].mn1 = tr[i].mx2 = lb; } else { if (ub < tr[i].mx1) tr[i].sum -= (tr[i].mx1 - ub) * tr[i].mxc, tr[i].mx1 = ub; if (tr[i].mn1 < lb) tr[i].sum += (lb - tr[i].mn1) * tr[i].mnc, tr[i].mn1 = lb; } tr[i].sum += bi * len[i]; tr[i].mx1 += bi, tr[i].mx2 += bi; tr[i].mn1 += bi, tr[i].mn2 += bi; lb -= tbi[i], ub -= tbi[i], tbi[i] += bi; if (tub[i] < lb) tub[i] = lb; if (ub < tlb[i]) tlb[i] = ub; tlb[i] = std::max(tlb[i], lb); tub[i] = std::min(tub[i], ub); } inline void Pushdown(int i) { if (tlb[i] != -Inf || tub[i] != Inf || tbi[i]) { P(li, tlb[i], tub[i], tbi[i]); P(ri, tlb[i], tub[i], tbi[i]); tlb[i] = -Inf, tub[i] = Inf, tbi[i] = 0; } } void Build(int i, int l, int r) { len[i] = r - l + 1; if (l == r) { LL x; scanf("%lld", &x); tr[i].sum = tr[i].mx1 = tr[i].mn1 = x; tr[i].mx2 = -Inf, tr[i].mn2 = Inf; tr[i].mxc = tr[i].mnc = 1; // printf("[%d : %d - %d] : %s\n", i, l, r, tr[i].Print()); return ; } Build(ls), Build(rs); tr[i] = tr[li] + tr[ri]; tlb[i] = -Inf, tub[i] = Inf, tbi[i] = 0; // printf("[%d : %d - %d] : %s\n", i, l, r, tr[i].Print()); } void Mdfmax(int i, int l, int r, int a, int b, LL x) { if (r < a || b < l || x <= tr[i].mn1) return ; if (a <= l && r <= b && x < tr[i].mn2) return P(i, x, Inf, 0)/*, printf("[%d : %d - %d] : %s\n", i, l, r, tr[i].Print()), void()*/; Pushdown(i), Mdfmax(ls, a, b, x), Mdfmax(rs, a, b, x); tr[i] = tr[li] + tr[ri]; // printf("[%d : %d - %d] : %s\n", i, l, r, tr[i].Print()); } void Mdfmin(int i, int l, int r, int a, int b, LL x) { if (r < a || b < l || tr[i].mx1 <= x) return ; if (a <= l && r <= b && tr[i].mx2 < x) return P(i, -Inf, x, 0)/*, printf("[%d : %d - %d] : %s\n", i, l, r, tr[i].Print()), void()*/; Pushdown(i), Mdfmin(ls, a, b, x), Mdfmin(rs, a, b, x); tr[i] = tr[li] + tr[ri]; // printf("[%d : %d - %d] : %s\n", i, l, r, tr[i].Print()); } void Mdfadd(int i, int l, int r, int a, int b, LL x) { if (r < a || b < l) return ; if (a <= l && r <= b) return P(i, -Inf, Inf, x)/*, printf("[%d : %d - %d] : %s\n", i, l, r, tr[i].Print()), void()*/; Pushdown(i), Mdfadd(ls, a, b, x), Mdfadd(rs, a, b, x); tr[i] = tr[li] + tr[ri]; // printf("[%d : %d - %d] : %s\n", i, l, r, tr[i].Print()); } LL Qur(int i, int l, int r, int a, int b) { if (r < a || b < l) return 0; if (a <= l && r <= b) return tr[i].sum; Pushdown(i); return Qur(ls, a, b) + Qur(rs, a, b); } int main() { scanf("%d%d", &N, &Q); Build(1, 1, N); while (Q--) { int t, l, r; LL x; scanf("%d%d%d", &t, &l, &r), ++l; if (t < 3) { scanf("%lld", &x); (t ? t == 1 ? Mdfmax : Mdfadd : Mdfmin)(1, 1, N, l, r, x); } else printf("%lld\n", Qur(1, 1, N, l, r)); } return 0; } /* 5 3 -5 -6 7 -9 7 0 1 5 1 1 1 5 5 3 2 5 */