Lazy Segment Tree | Explained
Intution\n According to the contraints given in the problem its possible to store all data regarding x coordinates in a array. \n Lets have a array M such that 
Intution\n* According to the contraints given in the problem its possible to store all data regarding <code>x coordinates</code> in a array. \n* Lets have a array `M` such that `M[i] = largest size block that can be placed considering i to be the ending position of that box. `\n\nLets look at a dry run of this array M on example 2 `queries = [[1,7],[2,7,6],[1,2],[2,7,5],[2,7,6]]`\nIntial values\nM = `[0,1,2,3,4,5,6,7,8]`\n\nQuery 1 (1,7) Add an obstacle at x = 7\nM = `[0,1,2,3,4,5,6,0,1]`\n\nQuery 3 (1,2) Add an obstacle at x = 2\nM = `[0,1,0,1,2,3,4,0,1]`\n\nObserve at all coordinates `i` including `x`, `M[i] -= M[x]`. Here `i` is in range of `[x,next obstacle after x - 1]`\n\nTo answer queries of type 2 lets find the maximum in range `[0,x]`, lets name is `max`\n* if `max >= sz` there always exists position before x where `sz` sized block can be placed. answer true.\n* if `max == sz-1`  now we can consider the right end of the coordinate where there value would have been `max` value of M, as placing a box which touches a obstacle is allowed. But there is a catch here, if x is the only coordinate with `M[x] == max` then the answer is false, else answer is true\n* else answer is false. \n\nThis can be implemented with a lazy segment tree (Range Add, Range Maximum). I also used a `treeSet` for implementation. \n\nPlease do refer the code provided below, I you have any doubts please feel free to comment. \n\n```\nclass Solution{\n    public List<Boolean> getResults(int[][] queries) {\n        int N = 0; //Maximum value of x coordinate\n        for(int[] q: queries) N = Math.max(N,q[1]);\n        List<Boolean> answers = new ArrayList<>();\n        TreeSet<Integer> treeSet = new TreeSet<>();\n        MassAddMaximumSegmentTree M = new MassAddMaximumSegmentTree(N+2);\n        for(int i=0;i<N+2;i++) M.addToRange(i,i,i); //Initialize M array\n        for(int[] q: queries){\n            int x = q[1];\n            if(q[0] == 2){\n                int sz = q[2];\n                long max = M.getMaximumInRange(0,x);\n                if(max >= sz) answers.add(true); //case 1\n                else if(max == sz - 1){\n                    if(M.getMaximumInRange(x,x) != max) answers.add(true); //There exists a place left to x where M[i] is max\n                    else{ //Now M[x] == max, lets check if there exists some i where M[i] == max\n                        Integer PREV = treeSet.floor(x);\n                        if(PREV != null){\n                            if(M.getMaximumInRange(0,PREV) >= sz+1) answers.add(true);\n                            else answers.add(false);\n                        }\n                        else answers.add(false); //There were no obstacles in range (0,x) so answer is false\n                    }\n                }\n                else answers.add(false);\n            }\n            else{\n                Integer NEXT = treeSet.ceiling(x);\n                int next;\n                if(NEXT == null) next = N+1;\n                else next = NEXT;\n                M.addToRange(x,next-1,-1*(M.getMaximumInRange(x,x))); //Subtract the contribution of M[x]\n                treeSet.add(x);\n            }\n        }\n        return answers;\n    }\n}\nclass MassAddMaximumSegmentTree {\n    long[] segmentArray;\n    long[] lazy;\n    int length;\n\n    public MassAddMaximumSegmentTree(int n){\n        this.length = n;\n        int height = (int)Math.ceil(Math.log(length)/Math.log(2));\n        int lengthOfSegmentTree = 2*(1<<height)-1;\n        this.segmentArray = new long[lengthOfSegmentTree];\n        this.lazy = new long[lengthOfSegmentTree];\n    }\n\n    public void addToRange(int left, int right, long value){\n        add(0,length-1,0,left,right,value);\n    }\n    private long add(int ss, int se, int si, int qs, int qe, long value){\n        if(se<qs || qe<ss) return segmentArray[si];\n        if(ss != se) propagate(si);\n        if(qs<=ss && se<=qe){\n            lazy[si] += value;\n            return segmentArray[si] = segmentArray[si]+value;\n        }\n        int mid = (ss+se)>>1;\n        return segmentArray[si] = Math.max(add(ss,mid,2*si+1,qs,qe,value),add(mid+1,se,2*si+2,qs,qe,value));\n    }\n\n    public long getMaximumInRange(int left, int right){\n        return getMax(0,length-1,0,left,right);\n    }\n\n    private long getMax(int ss, int se, int si, int qs, int qe){\n        if(se<qs || qe<ss) return Long.MIN_VALUE;\n        if(ss != se) propagate(si);\n        if(qs<=ss && se<=qe) return segmentArray[si];\n        int mid = (ss+se)>>1;\n        return Math.max(getMax(ss,mid,2*si+1,qs,qe), getMax(mid+1,se,2*si+2,qs,qe));\n    }\n\n\n    private void propagate(int si){\n        if(lazy[si]!=0){\n            segmentArray[2*si+1] += lazy[si];\n            segmentArray[2*si+2] += lazy[si];\n            lazy[2*si+1] += lazy[si];\n            lazy[2*si+2] += lazy[si];\n            lazy[si] = 0;\n        }\n    }\n}\n```\n
['Tree', 'Java']