Easy Segment Tree + Lazy Propagation Problem || Easy to understand || Beats 100% || C++
Intuition\nInitialzie the Segment Tree with the values 0, 1, 2, 3, ... N, as the maximum distance possible, from 0 to each \'x\'. \nNow to get the Type 2 query,
# Intuition\n**Initialzie the Segment Tree with the values 0, 1, 2, 3, ... N, as the maximum distance possible, from 0 to each \'x\'. \nNow to get the Type 2 query, just query for the maximum in the segment (0,x).\nFor the Type 1 query, we block the position \'x\', hence, the positions next to x will get update to d - \'x\', which we just did using range update query. To update, we need to keep track of the next greater element, which is already blocked, since, we need to update till that point only, as after that point, the distance is already updated.\nSet is used to keep track of it.**\n# Complexity\n- Time complexity:$$O(nlogn)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:$$O(n)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n    int N = 50005;\n    int MAX = 4 * 50005 + 5;\n    int arr[50005];\n    int tree[4 * 50005 + 5];\n    int lazy[4 * 50005 + 5];\n\n    void build_tree(int node, int a, int b) {\n        if(a > b) return;\t\n        if(a == b) {\n            tree[node] = arr[a];\n            return;\n        }\n        build_tree(node*2, a, (a+b)/2);\n        build_tree(node*2+1, 1+(a+b)/2, b);\n        tree[node] = max(tree[node*2], tree[node*2+1]);\n    }\n\n    void update_tree(int node, int a, int b, int i, int j, int value) {\n        if(lazy[node] != 0) { \n            tree[node] += lazy[node]; \n            if(a != b) {\n                lazy[node*2] += lazy[node];\n                lazy[node*2+1] += lazy[node]; \n            }\n            lazy[node] = 0; \n        }\n        if(a > b || a > j || b < i)\n            return;\n        if(a >= i && b <= j) {\n            tree[node] += value;\n            if(a != b) { \n                lazy[node*2] += value;\n                lazy[node*2+1] += value;\n            }\n            return;\n        }\n        update_tree(node*2, a, (a+b)/2, i, j, value);\n        update_tree(1+node*2, 1+(a+b)/2, b, i, j, value);\n        tree[node] = max(tree[node*2], tree[node*2+1]); \n    }\n\n    int query_tree(int node, int a, int b, int i, int j) {\n        if(a > b || a > j || b < i) return -1e9; \n        if(lazy[node] != 0) {\n            tree[node] += lazy[node];\n            if(a != b) {\n                lazy[node*2] += lazy[node]; \n                lazy[node*2+1] += lazy[node]; \n            }\n            lazy[node] = 0; \n        }\n        if(a >= i && b <= j)\n            return tree[node];\n        int q1 = query_tree(node*2, a, (a+b)/2, i, j); \n        int q2 = query_tree(1+node*2, 1+(a+b)/2, b, i, j); \n        int res = max(q1, q2);\n        return res;\n    }\n    vector<bool> getResults(vector<vector<int>>& queries) {\n        for(int i=0; i<N; i++) arr[i] = i;\n        build_tree(1, 0, N-1);\n        memset(lazy, 0, sizeof lazy);\n        vector<bool> ans;\n        set<int> st;\n        st.insert(N-1);\n        for(auto &it: queries){\n            if(it[0] == 1){\n                int val = query_tree(1, 0, N-1, it[1], it[1]);\n                int nv = *st.lower_bound(it[1]);\n                update_tree(1, 0, N-1, it[1] + 1, nv, -1 * val);\n                st.insert(it[1]);\n            }else{\n                int val = query_tree(1, 0, N-1, 0, it[1]);\n                if(val >= it[2]) ans.push_back(1);\n                else ans.push_back(0);\n            }\n        }\n        return ans;\n    }\n};\n```
['C++']