/**
1. 左开右闭区间的范围维护:
    1.1 因为边界范围是 1e9, 所以不可能存每个数来查, 
    1.2 但是查询和写入次数较少所以可以维护顺序的二元组[left, right) 列表, 通过二分查找确定位置
    1.3 怎么快速二分查找, 并且动态添加删除 -> 平衡二叉查找树 -> TreeSet

2. 各操作
    1. 确定区间范围 [left, right) 区间应该扫描[-∞, left) 到 [right+1, +∞) 之间的所有区间
    2. add: 扩展可覆盖的交集, 并删除set内元素, 最后放入扩展后的区间
    3. del: in.left < left ,   说明原区间前面有切割剩余, 加入 [in.left, left)
            right < in.right , 说明原区间后面有切割剩余, 加入 [right, in.righ)
    4. query: [left, right) 只可能和两个区间相交: [left, right)  前面的区间a, 和 a后面的区间b ,如果a,b都不包含[left, right) ,返回 false
*/

class RangeModule {

    class Node{
        int left, right;
        public Node(int left, int right){
            this.left = left;
            this.right = right;
        } 
    }

    TreeSet<Node> data;
    public RangeModule() {
        data = new TreeSet<>((a,b)->(a.right == b.right ? a.left - b.left : a.right - b.right));
    }

    public void addRange(int left, int right) {
        Iterator<Node> it = data.tailSet(new Node(0, left)).iterator();
        while (it.hasNext()){
            Node node = it.next();
            if (right < node.left) break;
            left = Math.min(left, node.left);
            right = Math.max(right, node.right);
            it.remove();
        }
        data.add(new Node(left, right));
    }

    public boolean queryRange(int left, int right) {
        if (data.isEmpty()) return false;
        Node node = new Node(left, right);
        Node prev = data.lower(node);
        if (prev != null && prev.left <= left && right <= prev.right) return true;
        Node next = prev == null ? data.first() : data.higher(prev);
        if (next != null && next.left <= left && right <= next.right) return true;
        return false;
    }

    public void removeRange(int left, int right) {
        Iterator<Node> it = data.tailSet(new Node(0, left)).iterator();
        List<Node> buffer = new ArrayList<>();
        while (it.hasNext()){
            Node node = it.next();
            if (right < node.left) break;
            if (node.left < left)   buffer.add(new Node(node.left, left));
            if (right < node.right) buffer.add(new Node(right,  node.right));
            it.remove();
        }
        data.addAll(buffer);
    }
}

/**
 * Your RangeModule object will be instantiated and called as such:
 * RangeModule obj = new RangeModule();
 * obj.addRange(left,right);
 * boolean param_2 = obj.queryRange(left,right);
 * obj.removeRange(left,right);
 */