Advertisement
Guest User

Untitled

a guest
Mar 24th, 2018
67
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 5.84 KB | None | 0 0
  1. import java.io.*;
  2. import java.util.StringTokenizer;
  3.  
  4. public class rmq2 {
  5.  
  6.     private static long INF = (long) Math.pow(10, 18) + (long) 1;
  7.     private static long[] tAdd;
  8.     private static long[] tSet;
  9.     private static long[] t;
  10.     private static long[] a;
  11.  
  12.  
  13.     public static void main(String[] args) throws IOException {
  14.         Reader.init(new FileInputStream(new File("C:\\Users\\asus\\Desktop\\Kramer\\ЛабаДеревоОтрезков\\№3\\rmq2.in.txt")));
  15.         //Scanner input = new Scanner(new File("rsq.in"));
  16.         PrintWriter writer = new PrintWriter("C:\\Users\\asus\\Desktop\\Kramer\\ЛабаДеревоОтрезков\\№3\\rmq2.out.txt");
  17.         int n1 = Reader.nextInt();
  18.         int n2 = n1;
  19.         int k = 0;
  20.         while (n1 != 0) {
  21.             n1 = n1 / 2;
  22.             k++;
  23.         }
  24.         n1 = (int) Math.pow(2, k);
  25.         a = new long[n1];
  26.         for (int i = 0; i < n2; i++) {
  27.             a[i] = Reader.nextLong();
  28.         }
  29.         for (int i = n2; i < n1; i++) {
  30.             a[i] = INF;
  31.         }
  32.         /*
  33.         for (int i = 0; i < n1; i++) {
  34.             System.out.print(a[i] + " ");
  35.         }
  36.         System.out.println(n1);
  37.         */
  38.         t = new long[2 * n1 - 1];
  39.         t = build(0, 0, n1 - 1, a);
  40.         /*
  41.         for (int i = 0; i < t.length; i++) {
  42.             System.out.print(t[i] + " ");
  43.         }
  44.         */
  45.         tAdd = new long[2 * n1 - 1];
  46.         tSet = new long[2 * n1 - 1];
  47.         String op;
  48.         long x, i, j;
  49.         to:
  50.         while (true) {
  51.             try {
  52.                 op = Reader.next();
  53.                 if (op.equals("set")) {
  54.                     i = Reader.nextLong();
  55.                     j = Reader.nextLong();
  56.                     x = Reader.nextLong();
  57.                     modify(0, 0, n1 - 1, i - 1, j - 1, x, 0);
  58.                 } else if (op.equals("min")){
  59.                     i = Reader.nextLong();
  60.                     j = Reader.nextLong();
  61.                     long min = query(0, 0, n1 - 1, i - 1, j - 1);
  62.                     writer.println(min);
  63.                     /*
  64.                     System.out.println(min);
  65.                     for(int u = 0; u < 2 * n1 - 1; u++) {
  66.                         System.out.print(t[u] + " ");
  67.                     }
  68.                     System.out.println();
  69.                     */
  70.                 } else if (op.equals("add")) {
  71.                     i = Reader.nextLong();
  72.                     j = Reader.nextLong();
  73.                     x = Reader.nextLong();
  74.                     modify(0, 0, n1 - 1, i - 1, j -  1, 0, x);
  75.                 }
  76.             } catch(NullPointerException e) {
  77.                 break to;
  78.             }
  79.         }
  80.         writer.close();
  81.     }
  82.  
  83.     private static void push(long v, long vl, long vr) {
  84.         if (tSet[(int) v] != 0) {
  85.             t[(int) v] = tSet[(int) v];
  86.             if (vl != vr) {
  87.                 tSet[2 * (int) v + 1] = tSet[(int) v];
  88.                 tSet[2 * (int) v + 2] = tSet[(int) v];
  89.                 tAdd[2 * (int) v + 1] = 0;
  90.                 tAdd[2 * (int) v + 2] = 0;
  91.             }
  92.             tSet[(int) v] = 0;
  93.         }
  94.         if (tAdd[(int) v] != 0) {
  95.             t[(int) v] = t[(int) v] + tAdd[(int) v];
  96.             if (vl != vr) {
  97.                 tAdd[2 * (int) v + 1] = tAdd[2 * (int) v + 1] + tAdd[(int) v];
  98.                 tAdd[2 * (int) v + 2] = tAdd[2 * (int) v + 2] + tAdd[(int) v];
  99.             }
  100.             tAdd[(int) v ] = 0;
  101.         }
  102.     }
  103.  
  104.     private static long[] build(long v, long vl, long vr, long a[]) {
  105.         if (vl == vr) {
  106.             t[(int) v] = a[(int) vl];
  107.             return t;
  108.         }
  109.         long vm = vl + (vr - vl) / 2;
  110.         build(2 * v + 1, vl, vm, a);
  111.         build(2 * v + 2, vm + 1, vr, a);
  112.         t[(int) v] = min(t[2 * (int) v + 1], t[2 * (int) v + 2]);
  113.         return t;
  114.     }
  115.  
  116.     private static long query(long v, long vl, long vr, long l, long r) {
  117.         push(v, vl, vr);
  118.         if (r < vl || vr < l)
  119.             return INF;
  120.         if (l <= vl && vr <= r)
  121.             return t[(int) v];
  122.         long vm = vl + (vr - vl) / 2;
  123.         long ql = query(2 * v + 1, vl, vm, l, r);
  124.         long qr = query(2 * v + 2, vm + 1, vr, l, r);
  125.         return min(ql, qr);
  126.     }
  127.  
  128.     private static void modify(long v, long vl, long vr, long l, long r, long set, long add) {
  129.         push(v, vl, vr);
  130.         if (r < vl || vr < l)
  131.             return;
  132.         if (l <= vl && vr <= r) {
  133.             if (set != 0) {
  134.                 tSet[(int) v] = set;
  135.             }
  136.             if (add != 0) {
  137.                 tAdd[(int) v] = add;
  138.             }
  139.             push(v, vl, vr);
  140.             return;
  141.         }
  142.         long vm = vl + (vr - vl) / 2;
  143.         modify(2 * v + 1, vl, vm, l, r, set, add);
  144.         modify(2 * v + 2, vm + 1, vr, l, r, set, add);
  145.         t[(int) v] = min(t[2 * (int) v + 1], t[2 * (int) v + 2]);
  146.     }
  147.  
  148.     private static long min(long a, long b) {
  149.         if (a < b) {
  150.             return a;
  151.         } else {
  152.             return b;
  153.         }
  154.     }
  155.  
  156.     private static class Reader {
  157.         static BufferedReader reader;
  158.         static StringTokenizer tokenizer;
  159.  
  160.         static void init(InputStream input) {
  161.             reader = new BufferedReader(new InputStreamReader(input));
  162.             tokenizer = new StringTokenizer("");
  163.         }
  164.  
  165.         static String next() throws IOException {
  166.             while (!tokenizer.hasMoreTokens()) {
  167.                 //TODO add check for eof if necessary
  168.                 tokenizer = new StringTokenizer(reader.readLine());
  169.             }
  170.             return tokenizer.nextToken();
  171.         }
  172.  
  173.         static int nextInt() throws IOException {
  174.             return Integer.parseInt(next());
  175.         }
  176.  
  177.         static long nextLong() throws IOException {
  178.             return Long.parseLong(next());
  179.         }
  180.  
  181.     }
  182. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement