Advertisement
Guest User

Untitled

a guest
Mar 24th, 2018
58
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 4.99 KB | None | 0 0
  1. import java.io.*;
  2. import java.util.StringTokenizer;
  3.  
  4.  
  5. class Reader {
  6.     static BufferedReader reader;
  7.     static StringTokenizer tokenizer;
  8.  
  9.     static void init(InputStream input) {
  10.         reader = new BufferedReader(
  11.                 new InputStreamReader(input));
  12.         tokenizer = new StringTokenizer("");
  13.     }
  14.  
  15.     static String next() throws IOException {
  16.         while (!tokenizer.hasMoreTokens()) {
  17.             if (!reader.ready())
  18.                 return "";
  19.             tokenizer = new StringTokenizer(
  20.                     reader.readLine());
  21.         }
  22.         return tokenizer.nextToken();
  23.     }
  24.  
  25.     static int nextInt() throws IOException {
  26.         return Integer.parseInt(next());
  27.     }
  28.  
  29.     static long nextLong() throws IOException {
  30.         return Long.parseLong(next());
  31.     }
  32.  
  33.     static double nextDouble() throws IOException {
  34.         return Double.parseDouble(next());
  35.     }
  36.  
  37. }
  38.  
  39. public class RMQ2 {
  40.  
  41.     private static long[] t, add;
  42.     private static Long[] set;
  43.  
  44.     private static void build(int v, long vl, long vr, long[] a) {
  45.         add[v] = 0;
  46.         set[v] = null;
  47.         if (vl == vr) {
  48.             t[v] = a[(int) vl];
  49.             return;
  50.         }
  51.         long vm = vl + (vr - vl) / 2;
  52.         build(2 * v + 1, vl, vm, a);
  53.         build(2 * v + 2, vm + 1, vr, a);
  54.         t[v] = Math.min(t[2 * v + 1], t[2 * v + 2]);
  55.     }
  56.  
  57.     private static void push(int v, long vl, long vr) {
  58.         if (set[v] != null) {
  59.             t[v] = set[v];
  60.             if (vl != vr) {
  61.                 set[2 * v + 1] = set[v];
  62.                 set[2 * v + 2] = set[v];
  63.                 add[2 * v + 1] = 0;
  64.                 add[2 * v + 2] = 0;
  65.             }
  66.             set[v] = null;
  67.         }
  68.         if (add[v] != 0) {
  69.             t[v] += add[v];
  70.             if (vl != vr) {
  71.                 add[2 * v + 1] += add[v];
  72.                 add[2 * v + 2] += add[v];
  73.             }
  74.             add[v] = 0;
  75.         }
  76.     }
  77.  
  78.     private static long query(int v, long vl, long vr, long l, long r) {
  79.         push(v, vl, vr);
  80.         if (r < vl || vr < l)
  81.             return Long.MAX_VALUE;
  82.         if (l <= vl && vr <= r)
  83.             return t[v];
  84.         long vm = vl + (vr - vl) / 2;
  85.         long ql = query(2 * v + 1, vl, vm, l, r);
  86.         long qr = query(2 * v + 2, vm + 1, vr, l, r);
  87.         return Math.min(ql, qr);
  88.     }
  89.  
  90.     private static void modifySet(int v, long vl, long vr, long l, long r, Long setValue) {
  91.         push(v, vl, vr);
  92.         if (r < vl || vr < l)
  93.             return;
  94.         if (l <= vl && vr <= r) {
  95.             set[v] = setValue;
  96.             add[v] = 0;
  97.             push(v, vl, vr);
  98.             return;
  99.         }
  100.         long vm = vl + (vr - vl) / 2;
  101.         modifySet(2 * v + 1, vl, vm, l, r, setValue);
  102.         modifySet(2 * v + 2, vm + 1, vr, l, r, setValue);
  103.         t[v] = Math.min(t[v * 2 + 1], t[v * 2 + 2]);
  104.     }
  105.  
  106.     private static void modifyAdd(int v, long vl, long vr, long l, long r, long addValue) {
  107.         push(v, vl, vr);
  108.         if (r < vl || vr < l)
  109.             return;
  110.         if (l <= vl && vr <= r) {
  111.             if (addValue != 0)
  112.                 add[v] = addValue;
  113.             push(v, vl, vr);
  114.             return;
  115.         }
  116.         long vm = vl + (vr - vl) / 2;
  117.         modifyAdd(2 * v + 1, vl, vm, l, r, addValue);
  118.         modifyAdd(2 * v + 2, vm + 1, vr, l, r, addValue);
  119.         t[v] = Math.min(t[v * 2 + 1], t[v * 2 + 2]);
  120.     }
  121.  
  122.     public static void main(String[] args) throws IOException {
  123.         Reader.init(new FileInputStream(new File("rmq2.in")));
  124.         try (BufferedWriter writer = new BufferedWriter(new FileWriter("rmq2.out"))) {
  125.             int n = Reader.nextInt();
  126.             t = new long[4 * n];
  127.             add = new long[4 * n];
  128.             set = new Long[4 * n];
  129.             long[] array = new long[n];
  130.             for (int i = 0; i != n; i++) {
  131.                 array[i] = Reader.nextLong();
  132.             }
  133.             build(0, 0, n - 1, array);
  134.             long val, l, r;
  135.             String input = "xd";
  136.             while (!input.equals("")) {
  137.                 input = Reader.next();
  138.                 switch (input) {
  139.                     case "min":
  140.                         l = Reader.nextLong();
  141.                         r = Reader.nextLong();
  142.                         writer.write(query(0, 0, n - 1, l - 1, r - 1) + "\n");
  143.                         break;
  144.                     case "set":
  145.                         l = Reader.nextLong();
  146.                         r = Reader.nextLong();
  147.                         val = Reader.nextLong();
  148.                         modifySet(0, 0, n - 1, l - 1, r - 1, val);
  149.                         break;
  150.                     case "add":
  151.                         l = Reader.nextLong();
  152.                         r = Reader.nextLong();
  153.                         val = Reader.nextLong();
  154.                         modifyAdd(0, 0, n - 1, l - 1, r - 1, val);
  155.                         break;
  156.                 }
  157.             }
  158.         }
  159.     }
  160. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement