BOJ. Digital Video Disk (9345)

Problem link · 한국어 · 日本語

Iterative segment tree for DVD permutations

The array starts as the permutation 0, 1, ..., N - 1. A type-0 operation swaps the values at two positions, and a type-1 operation asks whether the interval [A, B] currently contains exactly the DVDs numbered A through B.

For a permutation, that condition is equivalent to min(A..B) == A and max(A..B) == B: the interval has B - A + 1 distinct values, all within [A, B], so if both endpoints occur as its minimum and maximum, every value in between must occur as well. Conversely, if the interval contains exactly the required DVDs, its minimum and maximum are those endpoints.

The iterative segment tree stores the minimum and maximum for each segment. Leaves at indices size + i represent array position i, where size is the smallest power of two at least N. Each internal node stores the minimum and maximum of its two children. A point update replaces one leaf and recomputes every ancestor, so after swapping two positions we update both leaves. A range query walks upward over the half-open leaf interval [A, B + 1), combining only the covered nodes. The empty padding leaves are initialized to Integer.MAX_VALUE for minimum and Integer.MIN_VALUE for maximum, so they do not affect a query.

Both point updates and range queries take O(log N) time; the tree and permutation use O(N) space. This also handles N = 1: the single leaf answers the interval [0, 0] correctly.

Java

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

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

        while (testCases-- > 0) {
            int n = input.nextInt();
            int operations = input.nextInt();
            int[] dvdAt = new int[n];
            for (int i = 0; i < n; i++) {
                dvdAt[i] = i;
            }

            int size = 1;
            while (size < n) {
                size <<= 1;
            }
            int[] minTree = new int[size << 1];
            int[] maxTree = new int[size << 1];
            for (int i = 0; i < size; i++) {
                int value = i < n ? dvdAt[i] : Integer.MAX_VALUE;
                minTree[size + i] = value;
                maxTree[size + i] = i < n ? dvdAt[i] : Integer.MIN_VALUE;
            }
            for (int node = size - 1; node > 0; node--) {
                minTree[node] = Math.min(minTree[node << 1], minTree[node << 1 | 1]);
                maxTree[node] = Math.max(maxTree[node << 1], maxTree[node << 1 | 1]);
            }

            for (int operation = 0; operation < operations; operation++) {
                int type = input.nextInt();
                int a = input.nextInt();
                int b = input.nextInt();
                if (type == 0) {
                    int valueA = dvdAt[a];
                    int valueB = dvdAt[b];
                    dvdAt[a] = valueB;
                    dvdAt[b] = valueA;
                    update(minTree, maxTree, size, a, valueB);
                    update(minTree, maxTree, size, b, valueA);
                } else {
                    int minimum = Integer.MAX_VALUE;
                    int maximum = Integer.MIN_VALUE;
                    int left = size + a;
                    int right = size + b + 1;
                    while (left < right) {
                        if ((left & 1) != 0) {
                            minimum = Math.min(minimum, minTree[left]);
                            maximum = Math.max(maximum, maxTree[left]);
                            left++;
                        }
                        if ((right & 1) != 0) {
                            --right;
                            minimum = Math.min(minimum, minTree[right]);
                            maximum = Math.max(maximum, maxTree[right]);
                        }
                        left >>= 1;
                        right >>= 1;
                    }
                    output.append(minimum == a && maximum == b ? "YES\n" : "NO\n");
                }
            }
        }

        System.out.print(output);
    }

    private static void update(int[] minTree, int[] maxTree, int size, int position, int value) {
        int node = size + position;
        minTree[node] = value;
        maxTree[node] = value;
        for (node >>= 1; node > 0; node >>= 1) {
            minTree[node] = Math.min(minTree[node << 1], minTree[node << 1 | 1]);
            maxTree[node] = Math.max(maxTree[node << 1], maxTree[node << 1 | 1]);
        }
    }

    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++];
        }

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

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