Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.io.*;
- import java.util.StringTokenizer;
- public class rmq2 {
- private static long INF = (long) Math.pow(10, 18) + (long) 1;
- private static long[] tAdd;
- private static long[] tSet;
- private static long[] t;
- private static long[] a;
- public static void main(String[] args) throws IOException {
- Reader.init(new FileInputStream(new File("C:\\Users\\asus\\Desktop\\Kramer\\ЛабаДеревоОтрезков\\№3\\rmq2.in.txt")));
- //Scanner input = new Scanner(new File("rsq.in"));
- PrintWriter writer = new PrintWriter("C:\\Users\\asus\\Desktop\\Kramer\\ЛабаДеревоОтрезков\\№3\\rmq2.out.txt");
- int n1 = Reader.nextInt();
- int n2 = n1;
- int k = 0;
- while (n1 != 0) {
- n1 = n1 / 2;
- k++;
- }
- n1 = (int) Math.pow(2, k);
- a = new long[n1];
- for (int i = 0; i < n2; i++) {
- a[i] = Reader.nextLong();
- }
- for (int i = n2; i < n1; i++) {
- a[i] = INF;
- }
- /*
- for (int i = 0; i < n1; i++) {
- System.out.print(a[i] + " ");
- }
- System.out.println(n1);
- */
- t = new long[2 * n1 - 1];
- t = build(0, 0, n1 - 1, a);
- /*
- for (int i = 0; i < t.length; i++) {
- System.out.print(t[i] + " ");
- }
- */
- tAdd = new long[2 * n1 - 1];
- tSet = new long[2 * n1 - 1];
- String op;
- long x, i, j;
- to:
- while (true) {
- try {
- op = Reader.next();
- if (op.equals("set")) {
- i = Reader.nextLong();
- j = Reader.nextLong();
- x = Reader.nextLong();
- modify(0, 0, n1 - 1, i - 1, j - 1, x, 0);
- } else if (op.equals("min")){
- i = Reader.nextLong();
- j = Reader.nextLong();
- long min = query(0, 0, n1 - 1, i - 1, j - 1);
- writer.println(min);
- /*
- System.out.println(min);
- for(int u = 0; u < 2 * n1 - 1; u++) {
- System.out.print(t[u] + " ");
- }
- System.out.println();
- */
- } else if (op.equals("add")) {
- i = Reader.nextLong();
- j = Reader.nextLong();
- x = Reader.nextLong();
- modify(0, 0, n1 - 1, i - 1, j - 1, 0, x);
- }
- } catch(NullPointerException e) {
- break to;
- }
- }
- writer.close();
- }
- private static void push(long v, long vl, long vr) {
- if (tSet[(int) v] != 0) {
- t[(int) v] = tSet[(int) v];
- if (vl != vr) {
- tSet[2 * (int) v + 1] = tSet[(int) v];
- tSet[2 * (int) v + 2] = tSet[(int) v];
- tAdd[2 * (int) v + 1] = 0;
- tAdd[2 * (int) v + 2] = 0;
- }
- tSet[(int) v] = 0;
- }
- if (tAdd[(int) v] != 0) {
- t[(int) v] = t[(int) v] + tAdd[(int) v];
- if (vl != vr) {
- tAdd[2 * (int) v + 1] = tAdd[2 * (int) v + 1] + tAdd[(int) v];
- tAdd[2 * (int) v + 2] = tAdd[2 * (int) v + 2] + tAdd[(int) v];
- }
- tAdd[(int) v ] = 0;
- }
- }
- private static long[] build(long v, long vl, long vr, long a[]) {
- if (vl == vr) {
- t[(int) v] = a[(int) vl];
- return t;
- }
- long vm = vl + (vr - vl) / 2;
- build(2 * v + 1, vl, vm, a);
- build(2 * v + 2, vm + 1, vr, a);
- t[(int) v] = min(t[2 * (int) v + 1], t[2 * (int) v + 2]);
- return t;
- }
- private static long query(long v, long vl, long vr, long l, long r) {
- push(v, vl, vr);
- if (r < vl || vr < l)
- return INF;
- if (l <= vl && vr <= r)
- return t[(int) 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 min(ql, qr);
- }
- private static void modify(long v, long vl, long vr, long l, long r, long set, long add) {
- push(v, vl, vr);
- if (r < vl || vr < l)
- return;
- if (l <= vl && vr <= r) {
- if (set != 0) {
- tSet[(int) v] = set;
- }
- if (add != 0) {
- tAdd[(int) v] = add;
- }
- push(v, vl, vr);
- return;
- }
- long vm = vl + (vr - vl) / 2;
- modify(2 * v + 1, vl, vm, l, r, set, add);
- modify(2 * v + 2, vm + 1, vr, l, r, set, add);
- t[(int) v] = min(t[2 * (int) v + 1], t[2 * (int) v + 2]);
- }
- private static long min(long a, long b) {
- if (a < b) {
- return a;
- } else {
- return b;
- }
- }
- private static 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()) {
- //TODO add check for eof if necessary
- 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());
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement