Java Solution || Segment Trees || Binary Search || Beats 100%
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nimport java.util.*;\n\nclass Solution {\n\n\n    static int dist[];\n    static int ans[];\n    static ArrayList<Integer> obstacle;\n\n    // Segment Tree\n\n    static void buildTree(int l, int r, int idx){\n        if(l==r){\n            ans[idx] = dist[l];\n            return;\n        }\n\n        int mid = l+(r-l)/2;\n        buildTree(l,mid,2*idx+1);\n        buildTree(mid+1,r,2*idx+2);\n        ans[idx] = Math.max(ans[2*idx+1],ans[2*idx+2]);\n    }\n\n    static int findMax(int l, int r, int left, int right, int idx){\n        if(r<left || l>right) return Integer.MIN_VALUE;\n        if(l>=left && r<=right) return ans[idx];\n\n        int mid = l+(r-l)/2;\n        int a = findMax(l,mid,left,right,2*idx+1);\n        int b = findMax(mid+1,r,left,right,2*idx+2);\n        return Math.max(a,b);\n    }\n\n    static void update(int l, int r, int idx, int pos, int val){\n        if(l==r){\n            ans[idx] = val;\n            return;\n        }\n\n        int mid = l+(r-l)/2;\n        if(pos<=mid) update(l,mid,2*idx+1,pos,val);\n        else update(mid+1,r,2*idx+2,pos,val);\n        ans[idx] = Math.max(ans[2*idx+1],ans[2*idx+2]);\n    }\n\n\n\n    // finding Next and Prev Obstacle\n\n\n    public static int findNext(int x) {\n        int left = 0;\n        int right = obstacle.size() - 1;\n        int result = -1; \n\n        while (left <= right) {\n            int mid = left + (right - left) / 2;\n\n            if (obstacle.get(mid) > x) {\n                result = mid; \n                right = mid - 1; \n            } else {\n                left = mid + 1; \n            }\n        }\n        return result;\n    }\n\n    public static int findPrev(int x) {\n        int left = 0;\n        int right = obstacle.size() - 1;\n        int result = -1; \n\n        while (left <= right) {\n            int mid = left + (right - left) / 2;\n\n            if (obstacle.get(mid) < x) {\n                result = mid;\n                left = mid + 1; \n            } else {\n                right = mid - 1; \n            }\n        }\n        return result;\n    }\n\n\n\n    // Actual code\n\n    public static List<Boolean> getResults(int[][] q){\n\n        int n = Math.min(50004,3*q.length)+5;\n\n\n        dist = new int[n];\n        ans = new int[4*n];\n        obstacle = new ArrayList<>();\n        obstacle.add(0);\n        obstacle.add(n-1);\n        List<Boolean> a = new ArrayList<>();\n        dist[n-1] = n-1;\n        buildTree(0,n-1,0);\n\n\n\n\n        boolean flag = true;\n\n        for(int i=0; i<q.length; i++){\n            int type = q[i][0];\n            int x = q[i][1];\n            if(type==1){\n                flag = false;\n\n                int nx = findNext(x);\n                int pr = findPrev(x);\n\n                int next = obstacle.get(nx);\n                int prev = obstacle.get(pr);\n                obstacle.add(nx,x);\n\n                dist[x] = x-prev;\n                update(0,n-1,0,x,x-prev);\n                dist[next] = next-x;\n                update(0,n-1,0,next,next-x);\n\n\n\n\n            }else{\n                int sz = q[i][2];\n                int prev = findPrev(x);\n                int max = findMax(0,n-1,0,obstacle.get(prev),0);\n                max = Math.max(max,x-obstacle.get(prev));\n\n                if(flag) max = x-obstacle.get(prev);\n\n\n                if(sz<=max) a.add(true);\n                else a.add(false);\n            }\n\n\n        }\n        return a;\n    }\n\n    public static void main(String[] args) {\n        int q[][] = {{2,3,1}};\n        System.out.println(getResults(q));\n    }\n}\n```
['Java']