Submit Info #14046

Problem Lang User Status Time Memory
Range Chmin Chmax Add Range Sum java dalt AC 828 ms 66.85 MiB

ケース詳細
Name Status Time Memory
example_00 AC 77 ms 20.04 MiB
max_random_00 AC 800 ms 66.85 MiB
max_random_01 AC 824 ms 66.80 MiB
max_random_02 AC 828 ms 66.71 MiB
medium_00 AC 104 ms 21.60 MiB
medium_01 AC 113 ms 21.48 MiB
medium_02 AC 112 ms 21.48 MiB
random_00 AC 664 ms 54.23 MiB
random_01 AC 672 ms 57.97 MiB
random_02 AC 502 ms 41.39 MiB
small_00 AC 69 ms 19.98 MiB
small_01 AC 78 ms 20.09 MiB
small_02 AC 71 ms 19.90 MiB
small_03 AC 75 ms 20.08 MiB
small_04 AC 71 ms 19.97 MiB
small_05 AC 76 ms 20.10 MiB
small_06 AC 75 ms 20.00 MiB
small_07 AC 77 ms 20.05 MiB
small_08 AC 71 ms 20.07 MiB
small_09 AC 69 ms 19.89 MiB

import java.io.OutputStream; import java.io.IOException; import java.io.InputStream; import java.io.OutputStream; import java.io.IOException; import java.io.UncheckedIOException; import java.io.Closeable; import java.io.Writer; import java.io.OutputStreamWriter; import java.io.InputStream; /** * Built using CHelper plug-in * Actual solution is at the top */ public class Main { public static void main(String[] args) throws Exception { Thread thread = new Thread(null, new TaskAdapter(), "", 1 << 29); thread.start(); thread.join(); } static class TaskAdapter implements Runnable { @Override public void run() { InputStream inputStream = System.in; OutputStream outputStream = System.out; FastInput in = new FastInput(inputStream); FastOutput out = new FastOutput(outputStream); RangeChminChmaxAddRangeSum solver = new RangeChminChmaxAddRangeSum(); solver.solve(1, in, out); out.close(); } } static class RangeChminChmaxAddRangeSum { public void solve(int testNumber, FastInput in, FastOutput out) { int n = in.readInt(); int q = in.readInt(); long[] a = new long[n]; in.populate(a); SegmentBeatExt ext = new SegmentBeatExt(0, n - 1, i -> a[i]); for (int i = 0; i < q; i++) { int t = in.readInt(); int l = in.readInt(); int r = in.readInt() - 1; if (t == 0) { //set min long b = in.readLong(); ext.updateMin(l, r, 0, n - 1, b); } else if (t == 1) { //set max long b = in.readLong(); ext.updateMax(l, r, 0, n - 1, b); } else if (t == 2) { //update long b = in.readLong(); ext.update(l, r, 0, n - 1, b); } else { //query long sum = ext.querySum(l, r, 0, n - 1); out.println(sum); } } } } static class SegmentBeatExt implements Cloneable { private static long inf = (long) 2e18; private SegmentBeatExt left; private SegmentBeatExt right; private long firstLargest; private long secondLargest; private int firstLargestCnt; private long firstSmallest; private long secondSmallest; private int firstSmallestCnt; private long dirty; private int size; private long sum; private void setMin(long x) { if (firstLargest <= x) { return; } sum -= (firstLargest - x) * firstLargestCnt; firstLargest = x; if (firstSmallest >= x) { firstSmallest = x; firstSmallestCnt = size; } secondSmallest = Math.min(secondSmallest, x); if (secondSmallest == firstSmallest) { secondSmallest = inf; } } private void setMax(long x) { if (firstSmallest >= x) { return; } sum += (x - firstSmallest) * firstSmallestCnt; firstSmallest = x; if (firstLargest <= x) { firstLargest = x; firstLargestCnt = size; } secondLargest = Math.max(secondLargest, x); if (secondLargest == firstLargest) { secondLargest = -inf; } } private void modify(long x) { dirty += x; sum += x * size; firstSmallest += x; firstLargest += x; secondSmallest += x; secondLargest += x; } public void pushUp() { firstLargest = Math.max(left.firstLargest, right.firstLargest); secondLargest = Math.max(left.firstLargest == firstLargest ? left.secondLargest : left.firstLargest, right.firstLargest == firstLargest ? right.secondLargest : right.firstLargest); firstLargestCnt = (left.firstLargest == firstLargest ? left.firstLargestCnt : 0) + (right.firstLargest == firstLargest ? right.firstLargestCnt : 0); firstSmallest = Math.min(left.firstSmallest, right.firstSmallest); secondSmallest = Math.min(left.firstSmallest == firstSmallest ? left.secondSmallest : left.firstSmallest, right.firstSmallest == firstSmallest ? right.secondSmallest : right.firstSmallest); firstSmallestCnt = (left.firstSmallest == firstSmallest ? left.firstSmallestCnt : 0) + (right.firstSmallest == firstSmallest ? right.firstSmallestCnt : 0); sum = left.sum + right.sum; size = left.size + right.size; } public void pushDown() { if (dirty != 0) { left.modify(dirty); right.modify(dirty); dirty = 0; } left.setMin(firstLargest); right.setMin(firstLargest); left.setMax(firstSmallest); right.setMax(firstSmallest); } public SegmentBeatExt(int l, int r, IntToLongFunction func) { if (l < r) { int m = DigitUtils.floorAverage(l, r); left = new SegmentBeatExt(l, m, func); right = new SegmentBeatExt(m + 1, r, func); pushUp(); } else { sum = firstSmallest = firstLargest = func.apply(l); firstSmallestCnt = firstLargestCnt = 1; secondSmallest = inf; secondLargest = -inf; size = 1; } } private boolean covered(int ll, int rr, int l, int r) { return ll <= l && rr >= r; } private boolean noIntersection(int ll, int rr, int l, int r) { return ll > r || rr < l; } public void updateMin(int ll, int rr, int l, int r, long x) { if (noIntersection(ll, rr, l, r)) { return; } if (covered(ll, rr, l, r)) { if (firstLargest <= x) { return; } if (secondLargest < x) { setMin(x); return; } } pushDown(); int m = DigitUtils.floorAverage(l, r); left.updateMin(ll, rr, l, m, x); right.updateMin(ll, rr, m + 1, r, x); pushUp(); } public void updateMax(int ll, int rr, int l, int r, long x) { if (noIntersection(ll, rr, l, r)) { return; } if (covered(ll, rr, l, r)) { if (firstSmallest >= x) { return; } if (secondSmallest > x) { setMax(x); return; } } pushDown(); int m = DigitUtils.floorAverage(l, r); left.updateMax(ll, rr, l, m, x); right.updateMax(ll, rr, m + 1, r, x); pushUp(); } public void update(int ll, int rr, int l, int r, long x) { if (noIntersection(ll, rr, l, r)) { return; } if (covered(ll, rr, l, r)) { modify(x); return; } pushDown(); int m = DigitUtils.floorAverage(l, r); left.update(ll, rr, l, m, x); right.update(ll, rr, m + 1, r, x); pushUp(); } public long querySum(int ll, int rr, int l, int r) { if (noIntersection(ll, rr, l, r)) { return 0; } if (covered(ll, rr, l, r)) { return sum; } pushDown(); int m = DigitUtils.floorAverage(l, r); return left.querySum(ll, rr, l, m) + right.querySum(ll, rr, m + 1, r); } private SegmentBeatExt deepClone() { SegmentBeatExt seg = clone(); if (seg.left != null) { seg.left = seg.left.deepClone(); } if (seg.right != null) { seg.right = seg.right.deepClone(); } return seg; } protected SegmentBeatExt clone() { try { return (SegmentBeatExt) super.clone(); } catch (CloneNotSupportedException e) { throw new RuntimeException(e); } } private void toString(StringBuilder builder) { if (left == null && right == null) { builder.append(sum).append(","); return; } pushDown(); left.toString(builder); right.toString(builder); } public String toString() { StringBuilder builder = new StringBuilder(); deepClone().toString(builder); if (builder.length() > 0) { builder.setLength(builder.length() - 1); } return builder.toString(); } } static class DigitUtils { private DigitUtils() { } public static int floorAverage(int x, int y) { return (x & y) + ((x ^ y) >> 1); } } static class FastOutput implements AutoCloseable, Closeable, Appendable { private StringBuilder cache = new StringBuilder(10 << 20); private final Writer os; public FastOutput append(CharSequence csq) { cache.append(csq); return this; } public FastOutput append(CharSequence csq, int start, int end) { cache.append(csq, start, end); return this; } public FastOutput(Writer os) { this.os = os; } public FastOutput(OutputStream os) { this(new OutputStreamWriter(os)); } public FastOutput append(char c) { cache.append(c); return this; } public FastOutput append(long c) { cache.append(c); return this; } public FastOutput println(long c) { return append(c).println(); } public FastOutput println() { cache.append(System.lineSeparator()); return this; } public FastOutput flush() { try { os.append(cache); os.flush(); cache.setLength(0); } catch (IOException e) { throw new UncheckedIOException(e); } return this; } public void close() { flush(); try { os.close(); } catch (IOException e) { throw new UncheckedIOException(e); } } public String toString() { return cache.toString(); } } static class FastInput { private final InputStream is; private byte[] buf = new byte[1 << 13]; private int bufLen; private int bufOffset; private int next; public FastInput(InputStream is) { this.is = is; } public void populate(long[] data) { for (int i = 0; i < data.length; i++) { data[i] = readLong(); } } private int read() { while (bufLen == bufOffset) { bufOffset = 0; try { bufLen = is.read(buf); } catch (IOException e) { bufLen = -1; } if (bufLen == -1) { return -1; } } return buf[bufOffset++]; } public void skipBlank() { while (next >= 0 && next <= 32) { next = read(); } } public int readInt() { int sign = 1; skipBlank(); if (next == '+' || next == '-') { sign = next == '+' ? 1 : -1; next = read(); } int val = 0; if (sign == 1) { while (next >= '0' && next <= '9') { val = val * 10 + next - '0'; next = read(); } } else { while (next >= '0' && next <= '9') { val = val * 10 - next + '0'; next = read(); } } return val; } public long readLong() { int sign = 1; skipBlank(); if (next == '+' || next == '-') { sign = next == '+' ? 1 : -1; next = read(); } long val = 0; if (sign == 1) { while (next >= '0' && next <= '9') { val = val * 10 + next - '0'; next = read(); } } else { while (next >= '0' && next <= '9') { val = val * 10 - next + '0'; next = read(); } } return val; } } static interface IntToLongFunction { long apply(int x); } }