699 falling squares

class Solution {
    private int MAXN = 2001;
    private int[] arr = new int[MAXN * 4];
    private int[] maxh = new int[MAXN * 4];
    private int[] change = new int[MAXN * 4];
    private boolean[] update = new boolean[MAXN * 4];
    
    public List<Integer> fallingSquares(int[][] positions) {
        List<Integer> ans = new ArrayList<>();
        int n = reduce(positions);
        int max = 0;
        for (int[] position : positions) {
            int l = search(arr, position[0], n);
            int r = search(arr, position[0] + position[1] - 1, n);
            int h = query(l, r, 1, n, 1);
            h += position[1];
            update(h, l, r, 1, n, 1);
            max = Math.max(h, max);
            ans.add(max);
        }
        return ans;
    }
    
    private void update(int val, int jobl, int jobr, int left, int right, int idx) {
        if (left >= jobl && right <= jobr) {
            lazy(val, idx);
            return;
        }
        down(idx);
        int mid = (left + right) / 2;
        if (jobl <= mid) {
            update(val, jobl, jobr, left, mid, idx*2);
        }
        if (jobr > mid) {
            update(val, jobl, jobr, mid+1, right, idx*2+1);
        }
        maxh[idx] = Math.max(maxh[idx*2], maxh[idx*2+1]);
    }
    
    private void lazy(int val, int idx) {
        update[idx] = true;
        change[idx] = val;
        maxh[idx] = val;
    }
    
    private void down(int idx) {
        if (update[idx]) {
            lazy(change[idx], idx*2);
            lazy(change[idx], idx*2+1);
        }
        update[idx] = false;
    }
    
    private int query(int jobl, int jobr, int left, int right, int idx) {
        if (left >= jobl && right <= jobr) {
            return maxh[idx];
        }
        int mid = (left + right) / 2;
        down(idx);
        int h = 0;
        if (jobl <= mid) {
            h = Math.max(h, query(jobl, jobr, left, mid, idx*2));
        }
        if (jobr > mid) {
            h = Math.max(h, query(jobl, jobr, mid+1, right, idx*2+1));
        }
        return h;
    }
    
    private int search(int[] arr, int val, int n) {
        int l = 1;
        int r = n;
        while (l + 1 < r) {
            int m = (l + r) / 2;
            if (arr[m] == val) {
                return m;
            }
            if (arr[m] > val) {
                r = m;
            } else {
                l = m;
            }
        }
        if (arr[l] == val) {
            return l;
        }
        return r;
    }
    
    private int reduce(int[][] positions) {
        int size = 1;
        int n = 1;
        // start from 1
        for (int[] position : positions) {
            arr[size++] = position[0];
            arr[size++] = position[0] + position[1] - 1;
        }
        Arrays.sort(arr, 1, size);
        for (int i = 1; i < size; i++) {
            if (arr[n] != arr[i]) {
                arr[++n] = arr[i];
            }
        }
        return n;
    }
}

注意几个函数

update -> down + up + lazy

query -> down

down -> lazy

如何将离散的数据变紧凑，将数据sort并去重之后用它们的index作为range和range内的坐标

同时注意区间是左闭右开，右边界坐标总是-1