Balanced Lineup (POJ 3264)

It is a simple problem that need apply segment tree. We use two segment trees to maintain maximum and minimum values on the array respectively. Then when a query comes we return the difference of the maximum and minimum value we queried from these two segment trees.

import java.io.*;
import java.util.*;

public class BalancedLineUp {
    private static int queryMax(int[] maxtree, int k, int l, int r, int kl, int kr){
        if (r < kl || l > kr) {
            return Integer.MIN_VALUE;
        } else if (l <= kl && r >= kr) {
            return maxtree[k];
        } else {
            return Math.max(
                    queryMax(maxtree, k * 2 + 1, l, r, kl, (kl + kr) / 2),
                    queryMax(maxtree, k * 2 + 2, l, r, (kl + kr) / 2 + 1, kr));
        }
    }

    private static int queryMin(int[] mintree, int k, int l, int r, int kl, int kr){
        if (r < kl || l > kr) {
            return Integer.MAX_VALUE;
        } else if (l <= kl && r >= kr) {
            return mintree[k];
        } else {
            return Math.min(
                    queryMin(mintree, k * 2 + 1, l, r, kl, (kl + kr) / 2),
                    queryMin(mintree, k * 2 + 2, l, r, (kl + kr) / 2 + 1, kr));
        }
    }

    private static void solve(int[] heights, int[][] ranges) {

        int len = 1;
        while (len < heights.length) len <<= 1;

        int[] maxtree = new int[len * 2 - 1];
        int[] mintree = new int[len * 2 - 1];

        Arrays.fill(maxtree, Integer.MIN_VALUE);
        Arrays.fill(mintree, Integer.MAX_VALUE);

        for (int i = 0; i < heights.length; i++) {
            maxtree[i + len - 1] = heights[i];
            mintree[i + len - 1] = heights[i];
        }

        for (int i = len - 2; i >= 0; i--) {
            maxtree[i] = Math.max(maxtree[i * 2 + 1], maxtree[i * 2 + 2]);
            mintree[i] = Math.min(mintree[i * 2 + 1], mintree[i * 2 + 2]);
        }

        for (int i = 0; i < ranges.length; i++) {
            int l = ranges[i][0], r = ranges[i][1];
            System.out.println(queryMax(maxtree, 0, l, r, 0, len - 1) - queryMin(mintree, 0, l, r, 0, len - 1));
        }

    }

    public static void main(String[] args) {
        Scanner stdin = new Scanner(System.in);

        while (stdin.hasNextInt()) {
            int n = stdin.nextInt();
            int q = stdin.nextInt();

            int[] heights = new int[n];
            int[][] ranges = new int[q][2];

            for (int i = 0; i < heights.length; i++) {
                heights[i] = stdin.nextInt();
            }
            for (int i = 0; i < ranges.length; i++) {
                ranges[i][0] = stdin.nextInt() - 1;
                ranges[i][1] = stdin.nextInt() - 1;
            }

            solve(heights, ranges);
        }
    }
}