BOJ. Maximum and Minimum Values (2357)

BOJ 2357: Maximum and Minimum Values

Iterative segment tree

Store each input value at leaf n + i in two flat arrays. Every internal node combines its children: the minimum tree stores min(left, right), while the maximum tree stores max(left, right). This merge operation is associative, so a range can be split into disjoint tree segments and their results combined in any order.

For an inclusive 1-based query [a, b], convert it to the half-open 0-based interval [a - 1, b), represented by tree indices a - 1 + n and b + n. Move the left and right endpoints upward together. Whenever the left endpoint is a right child, include it and advance; whenever the right endpoint is a right boundary, move it left and include it. The sentinels Integer.MAX_VALUE for the minimum and Integer.MIN_VALUE for the maximum are identity values, so they do not affect any real result, including queries containing only negative or only positive values.

Building the two trees takes O(N) time and O(N) storage. Each query visits at most O(log N) levels and combines its selected segments in constant time per level, for O(log N) query time.

import java.io.BufferedInputStream;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        FastScanner input = new FastScanner();
        int n = input.nextInt();
        int queryCount = input.nextInt();

        int[] minTree = new int[2 * n];
        int[] maxTree = new int[2 * n];
        for (int i = 0; i < n; i++) {
            int value = input.nextInt();
            minTree[n + i] = value;
            maxTree[n + i] = value;
        }

        for (int i = n - 1; i > 0; i--) {
            minTree[i] = Math.min(minTree[2 * i], minTree[2 * i + 1]);
            maxTree[i] = Math.max(maxTree[2 * i], maxTree[2 * i + 1]);
        }

        StringBuilder output = new StringBuilder();
        for (int i = 0; i < queryCount; i++) {
            int left = input.nextInt() - 1 + n;
            int right = input.nextInt() + n;
            int minimum = Integer.MAX_VALUE;
            int maximum = Integer.MIN_VALUE;

            while (left < right) {
                if ((left & 1) == 1) {
                    minimum = Math.min(minimum, minTree[left]);
                    maximum = Math.max(maximum, maxTree[left]);
                    left++;
                }
                if ((right & 1) == 1) {
                    --right;
                    minimum = Math.min(minimum, minTree[right]);
                    maximum = Math.max(maximum, maxTree[right]);
                }
                left >>= 1;
                right >>= 1;
            }

            output.append(minimum).append(' ').append(maximum).append('\n');
        }
        System.out.print(output);
    }

    private static final class FastScanner {
        private final BufferedInputStream input = new BufferedInputStream(System.in);
        private final byte[] buffer = new byte[1 << 16];
        private int length;
        private int position;

        private int read() throws IOException {
            if (position == length) {
                length = input.read(buffer);
                position = 0;
                if (length == -1) return -1;
            }
            return buffer[position++];
        }

        int nextInt() throws IOException {
            int c;
            do {
                c = read();
            } while (c <= ' ' && c != -1);

            int sign = 1;
            if (c == '-') {
                sign = -1;
                c = read();
            }

            int value = 0;
            while (c > ' ') {
                value = value * 10 + c - '0';
                c = read();
            }
            return value * sign;
        }
    }
}