#1125738 (Java) No.1234 典型RMQ

• 問題: No.1234 典型RMQ
• ユーザー: 37zigen
• 提出日時: 2025-10-05 14:55:43
• 言語: Java (openjdk 23)
• 結果: AC
• 実行時間: 1,489 ms / 2,000 ms
• コード長: 8,175 bytes
• コンパイル時間: 3,826 ms
• コンパイル使用メモリ: 93,916 KB
• 実行使用メモリ: 144,912 KB
• 最終ジャッジ日時: 2025-10-05 14:57:18
• 合計ジャッジ時間: 28,883 ms
• ジャッジサーバーID （参考情報）: judge5 / judge4

ファイルパターン	結果
sample	AC * 3
other	AC * 27

ソースコード

import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.List;
import java.util.NoSuchElementException;
import java.util.function.IntFunction;
import java.util.stream.IntStream;
import java.util.stream.Stream;

class FastScanner {
    private static FastScanner instance = null;

    private final InputStream in = System.in;

    private final byte[] buffer = new byte[1024];

    private int ptr = 0;

    private int buflen = 0;

    // 外部から new できないようにする
    private FastScanner() {
    }

    public static FastScanner getInstance() {
        if (instance == null) {
            instance = new FastScanner();
        }
        return instance;
    }

    private boolean hasNextByte() {
        if (ptr < buflen) {
            return true;
        }
        ptr = 0;
        try {
            buflen = in.read(buffer);
        } catch (IOException e) {
            e.printStackTrace();
        }
        return buflen > 0;
    }

    private int readByte() {
        if (hasNextByte()) {
            return buffer[ptr++];
        } else {
            return -1;
        }
    }

    private boolean isPrintableChar(int c) {
        return (33 <= c) && (c <= 126);
    }

    public boolean hasNext() {
        while (hasNextByte() && (!isPrintableChar(buffer[ptr]))) {
            ptr++;
        } 
        return hasNextByte();
    }

    public long nextLong() {
        if (!hasNext()) {
            throw new NoSuchElementException();
        }
        long n = 0;
        boolean minus = false;
        int b = readByte();
        if (b == '-') {
            minus = true;
            b = readByte();
        }
        while ((b >= '0') && (b <= '9')) {
            n = (n * 10) + (b - '0');
            b = readByte();
        } 
        return minus ? -n : n;
    }

    public int nextInt() {
        return ((int) (nextLong()));
    }

    public long[] nextLongs(int n) {
        long[] a = new long[n];
        for (int i = 0; i < n; ++i) {
            a[i] = nextLong();
        }
        return a;
    }
}

abstract class MonoidAction<A extends Monoid<?>, X extends Monoid<?>> {
    public X merge(A a, X b) {
        if (a == null) {
            return b;
        }
        return mergeNonNull(a, b);
    }

    protected abstract X mergeNonNull(A a, X b);
}

/**
 * null は identity の代わり
 */
class LazySegTree<ActingMonoid extends Monoid<ActingMonoid>, ActedMonoid extends Monoid<ActedMonoid>> {
    int n = 1;

    ActedMonoid[] v;

    ActingMonoid[] lazy;

    private MonoidAction<ActingMonoid, ActedMonoid> ma;

    Object identity = null;

    @SuppressWarnings("unchecked")
    public LazySegTree(int n, MonoidAction<ActingMonoid, ActedMonoid> ma) {
        this.n = 2 * Integer.highestOneBit(n);
        v = ((ActedMonoid[]) (new Monoid[this.n * 2]));
        lazy = ((ActingMonoid[]) (new Monoid[this.n * 2]));
        this.ma = ma;
    }

    @SuppressWarnings("unchecked")
    public void build(ActedMonoid[] arr) {
        for (int i = 0; i < arr.length; ++i) {
            v[id(i, i + 1)] = arr[i];
        }
        for (int i = id(0, 1) - 1; i >= id(0, n); --i) {
            v[i] = merge(v[2 * i], v[(2 * i) + 1]);
        }
    }

    private void push(int k) {
        if (lazy[k] == identity) {
            return;
        }
        v[k] = ma.merge(((ActingMonoid) (lazy[k])), ((ActedMonoid) (v[k])));
        if (((2 * k) + 1) < v.length) {
            lazy[2 * k] = mergeLazy(lazy[k], lazy[2 * k]);
            lazy[(2 * k) + 1] = mergeLazy(lazy[k], lazy[(2 * k) + 1]);
        }
        lazy[k] = null;
    }

    public ActedMonoid query(int a, int b) {
        return query(a, b, null);
    }

    public ActedMonoid query(int a, int b, ActingMonoid add) {
        return query(0, n, a, b, 1, add);
    }

    private ActedMonoid query(int l, int r, int a, int b, int k, ActingMonoid add) {
        if (((a <= l) && (r <= b)) && (add != null)) {
            lazy[k] = mergeLazy(add, lazy[k]);
        }
        push(k);
        if ((a <= l) && (r <= b)) {
            return ((ActedMonoid) (v[k]));
        } else if ((r <= a) || (b <= l)) {
            return null;
        } else {
            int m = (l + r) / 2;
            ActedMonoid vl = query(l, m, a, b, 2 * k, add);
            ActedMonoid vr = query(m, r, a, b, (2 * k) + 1, add);
            v[k] = merge(v[2 * k], v[(2 * k) + 1]);
            return merge(vl, vr);
        }
    }

    private ActedMonoid merge(ActedMonoid a, ActedMonoid b) {
        if (a == identity) {
            return b;
        }
        if (b == identity) {
            return a;
        }
        return a.merge(b);
    }

    private ActingMonoid mergeLazy(ActingMonoid a, ActingMonoid b) {
        if (a == identity) {
            return b;
        }
        if (b == identity) {
            return a;
        }
        return a.merge(b);
    }

    int id(int a, int b) {
        int w = Integer.lowestOneBit(a ^ b);
        return (n / w) + (a / w);
    }
}

class AddArgMin<T extends Comparable<T>> extends MonoidAction<AddMonoid<T>, ArgMinMonoid<T>> {

    @Override
    protected ArgMinMonoid<T> mergeNonNull(AddMonoid<T> a, ArgMinMonoid<T> b) {
        return new ArgMinMonoid<>(b.pos, AddMonoid.add(a.val, b.val));
    }
}

class ArgMinMonoid<T extends Comparable<T>> extends Monoid<ArgMinMonoid<T>> {
    public int pos;

    public T val;

    public ArgMinMonoid(int pos, T val) {
        this.pos = pos;
        this.val = val;
    }

    @Override

    public ArgMinMonoid<T> merge(ArgMinMonoid<T> a) {
        return val.compareTo(a.val) <= 0 ? this : a;
    }
}

class AddMonoid<T> extends Monoid<AddMonoid<T>> {
    final T val;

    public AddMonoid(T val) {
        this.val = val;
    }

    @SuppressWarnings("unchecked")
    @Override

    public AddMonoid<T> merge(AddMonoid<T> a) {
        return new AddMonoid<>(add(val, a.val));
    }

    @SuppressWarnings("unchecked")

    public static <T> T add(T a, T b) {
        if ((a instanceof Integer av) && (b instanceof Integer bv)) {
            return ((T) (Integer.valueOf(av + bv)));
        } else if ((a instanceof Long av) && (b instanceof Long bv)) {
            return ((T) (Long.valueOf(av + bv)));
        } else if ((a instanceof Double av) && (b instanceof Double bv)) {
            return ((T) (Double.valueOf(av + bv)));
        } else if ((a instanceof Float av) && (b instanceof Float bv)) {
            return ((T) (Float.valueOf(av + bv)));
        } else {
            throw new UnsupportedOperationException("Unsupported numeric type: " + a.getClass());
        }
    }
}

abstract class Monoid<X> {
    public abstract X merge(X a);
}

class MyPrintWriter extends PrintWriter {
    private static MyPrintWriter instance = null;

    private MyPrintWriter() {
        super(System.out);
    }

    public static MyPrintWriter getInstance() {
        if (instance == null) {
            instance = new MyPrintWriter();
        }
        return instance;
    }
}

public class Main implements Runnable {
    public static void main(String[] args) throws IOException {
        new Thread(null, new Main(), "", (1024 * 1024) * 1024).start();// 1024MBスタックを確保して実行

    }

    @Override
    public void run() {
        FastScanner sc = FastScanner.getInstance();
        MyPrintWriter pw = MyPrintWriter.getInstance();
        int N = sc.nextInt();
        long[] A = sc.nextLongs(N);
        int Q = sc.nextInt();
        var tree = new LazySegTree<>(N, new AddArgMin<Long>());
        tree.build(IntStream.range(0, N).mapToObj(i -> new ArgMinMonoid<>(i, A[i])).toArray(ArgMinMonoid[]::new));
        for (int i = 0; i < Q; i++) {
            int type = sc.nextInt();
            int s = sc.nextInt() - 1;
            int t = sc.nextInt() - 1;
            long c = sc.nextLong();
            t++;
            if (type == 1) {
                tree.query(s, t, new AddMonoid<Long>(((long) (c))));
            } else {
                pw.println(tree.query(s, t).val);
            }
        }
        pw.close();
    }
}