Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.io.*;
- import java.util.StringTokenizer;
- class Reader {
- static BufferedReader reader;
- static StringTokenizer tokenizer;
- static void init(InputStream input) {
- reader = new BufferedReader(
- new InputStreamReader(input));
- tokenizer = new StringTokenizer("");
- }
- static String next() throws IOException {
- while (!tokenizer.hasMoreTokens()) {
- if (!reader.ready())
- return "";
- tokenizer = new StringTokenizer(
- reader.readLine());
- }
- return tokenizer.nextToken();
- }
- static int nextInt() throws IOException {
- return Integer.parseInt(next());
- }
- static long nextLong() throws IOException {
- return Long.parseLong(next());
- }
- static double nextDouble() throws IOException {
- return Double.parseDouble(next());
- }
- }
- public class RMQ2 {
- private static long[] t, add;
- private static Long[] set;
- private static void build(int v, long vl, long vr, long[] a) {
- add[v] = 0;
- set[v] = null;
- if (vl == vr) {
- t[v] = a[(int) vl];
- return;
- }
- long vm = vl + (vr - vl) / 2;
- build(2 * v + 1, vl, vm, a);
- build(2 * v + 2, vm + 1, vr, a);
- t[v] = Math.min(t[2 * v + 1], t[2 * v + 2]);
- }
- private static void push(int v, long vl, long vr) {
- if (set[v] != null) {
- t[v] = set[v];
- if (vl != vr) {
- set[2 * v + 1] = set[v];
- set[2 * v + 2] = set[v];
- add[2 * v + 1] = 0;
- add[2 * v + 2] = 0;
- }
- set[v] = null;
- }
- if (add[v] != 0) {
- t[v] += add[v];
- if (vl != vr) {
- add[2 * v + 1] += add[v];
- add[2 * v + 2] += add[v];
- }
- add[v] = 0;
- }
- }
- private static long query(int v, long vl, long vr, long l, long r) {
- push(v, vl, vr);
- if (r < vl || vr < l)
- return Long.MAX_VALUE;
- if (l <= vl && vr <= r)
- return t[v];
- long vm = vl + (vr - vl) / 2;
- long ql = query(2 * v + 1, vl, vm, l, r);
- long qr = query(2 * v + 2, vm + 1, vr, l, r);
- return Math.min(ql, qr);
- }
- private static void modifySet(int v, long vl, long vr, long l, long r, Long setValue) {
- push(v, vl, vr);
- if (r < vl || vr < l)
- return;
- if (l <= vl && vr <= r) {
- set[v] = setValue;
- add[v] = 0;
- push(v, vl, vr);
- return;
- }
- long vm = vl + (vr - vl) / 2;
- modifySet(2 * v + 1, vl, vm, l, r, setValue);
- modifySet(2 * v + 2, vm + 1, vr, l, r, setValue);
- t[v] = Math.min(t[v * 2 + 1], t[v * 2 + 2]);
- }
- private static void modifyAdd(int v, long vl, long vr, long l, long r, long addValue) {
- push(v, vl, vr);
- if (r < vl || vr < l)
- return;
- if (l <= vl && vr <= r) {
- if (addValue != 0)
- add[v] = addValue;
- push(v, vl, vr);
- return;
- }
- long vm = vl + (vr - vl) / 2;
- modifyAdd(2 * v + 1, vl, vm, l, r, addValue);
- modifyAdd(2 * v + 2, vm + 1, vr, l, r, addValue);
- t[v] = Math.min(t[v * 2 + 1], t[v * 2 + 2]);
- }
- public static void main(String[] args) throws IOException {
- Reader.init(new FileInputStream(new File("rmq2.in")));
- try (BufferedWriter writer = new BufferedWriter(new FileWriter("rmq2.out"))) {
- int n = Reader.nextInt();
- t = new long[4 * n];
- add = new long[4 * n];
- set = new Long[4 * n];
- long[] array = new long[n];
- for (int i = 0; i != n; i++) {
- array[i] = Reader.nextLong();
- }
- build(0, 0, n - 1, array);
- long val, l, r;
- String input = "xd";
- while (!input.equals("")) {
- input = Reader.next();
- switch (input) {
- case "min":
- l = Reader.nextLong();
- r = Reader.nextLong();
- writer.write(query(0, 0, n - 1, l - 1, r - 1) + "\n");
- break;
- case "set":
- l = Reader.nextLong();
- r = Reader.nextLong();
- val = Reader.nextLong();
- modifySet(0, 0, n - 1, l - 1, r - 1, val);
- break;
- case "add":
- l = Reader.nextLong();
- r = Reader.nextLong();
- val = Reader.nextLong();
- modifyAdd(0, 0, n - 1, l - 1, r - 1, val);
- break;
- }
- }
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement