A solution to Skyline

Main.java

import java.io.BufferedInputStream;
import java.io.BufferedOutputStream;
import java.io.PrintWriter;
import java.util.Scanner;

/*
    UVa 1232 - SKYLINE
    https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=3673
    https://uva.onlinejudge.org/external/12/1232.pdf
 */
public class Main {
    public static void main(String[] args) {
        final Scanner scanner = new Scanner(new BufferedInputStream(System.in));
        final PrintWriter writer = new PrintWriter(new BufferedOutputStream(System.out));
//        System.out.println("Where is runtime error..");
        int C = Integer.parseInt(scanner.next());
        while (C-- > 0) {
            int buildings = Integer.parseInt(scanner.next());
            final Tree tree = new Tree();
            int res = 0;
            int l, r, h;
            while (buildings-- > 0) {
                l = Integer.parseInt(scanner.next());
                r = Integer.parseInt(scanner.next());
                h = Integer.parseInt(scanner.next());
                tree.update(l, r, h);
//                System.out.println("Where is runtime error..");
                res += tree.search(l, r, h);
            }
//            System.out.println("Where is runtime error..");
            writer.println(res);

        }
        writer.flush();

//        scanner.nextInt(); // to read the last '0'
    }
}


class Node {
    public int left;
    public int right;
    public int maxHeight;
    public boolean isLeaf; // true if this is a leaf node

    public Node(int left, int right) {
        this(left, right, true);
    }

    public Node(int left, int right, boolean isLeaf) {
        this(left, right, isLeaf, 0);
    }

    public Node(int left, int right, boolean isLeaf, int maxHeight) {
        this.left = left;
        this.right = right;
        this.isLeaf = isLeaf;
        this.maxHeight = maxHeight;
    }
}

class Tree {
    Node[] nodes;

    public Tree() {
        nodes = new Node[100010 * 4 + 10];
        nodes[1] = new Node(1, 100000);
    }

    private int left(int idx) {
        return idx << 1;
    }

    private int right(int idx) {
        return (idx << 1) + 1;
    }

    public int search(int left, int right, int height) {
        return search(1, left, right, height);
    }

    private int search(int idx, int targetLeft, int targetRight, int targetHeight) {
        final Node curNode = nodes[idx];

        // curNode is completely out of target update range
        if (targetRight <= curNode.left || curNode.right <= targetLeft) return 0;

        // curNode is completely in target update range
        if (targetLeft <= curNode.left && curNode.right <= targetRight) {
            return (targetHeight >= curNode.maxHeight) ? (curNode.right - curNode.left) : 0;
        } else {
            return search(left(idx), targetLeft, targetRight, targetHeight)
                + search(right(idx), targetLeft, targetRight, targetHeight);
        }
    }

    public void update(int left, int right, int height) {
        update(1, left, right, height);

    }

    private void update(int idx, int targetLeft, int targetRight, int height) {
        final Node curNode = nodes[idx];

        // curNode is completely out of target update range
        if (targetRight <= curNode.left || curNode.right <= targetLeft) return;

        // curNode is completely in target update range
        if (targetLeft <= curNode.left && curNode.right <= targetRight) {
//            curNode.maxHeight = Math.max(curNode.maxHeight, height);
        } else {
            // curNode is partially in target update range
            if (curNode.isLeaf) {
                // need to split node
                if (targetRight < curNode.right) {
                    splitNode(idx, targetRight);
                } else if (curNode.left < targetLeft) {
                    splitNode(idx, targetLeft);
                }
            }
            update(left(idx), targetLeft, targetRight, height);
            update(right(idx), targetLeft, targetRight, height);
        }
        curNode.maxHeight = Math.max(curNode.maxHeight, height);
    }

    private void splitNode(int idx, int splitPoint) {
        nodes[idx].isLeaf = false;
        nodes[left(idx)] = new Node(nodes[idx].left, splitPoint, true, nodes[idx].maxHeight);
        nodes[right(idx)] = new Node(splitPoint, nodes[idx].right, true, nodes[idx].maxHeight);
    }
}