Segment tree.
Intuition\n Describe your first thoughts on how to solve this problem. \nThis problem is silly. Why not make it harder by handling arbitrary range queries?\n\n#
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThis problem is silly. Why not make it harder by handling arbitrary range queries?\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nSegment tree with point-wise updates. Query is: given a range `(lrange, rrange)`, compute longest subsequence of consecutive unallocated points. Each update allocates a specific point.\n\nApproach is: each node (over block `(left, right)`) stores its size, number of unallocated points in its, its suffix of each block, and largest number of consecutive unallocated points. Coalescing is a lot of casework, but not too difficult.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(q log n), where q is the number of queries and n is the maximum value x can take.\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(n log n).\n\n# Code\n```\nstruct node\n{\n    int sz;\n    int big;\n    int left;\n    int right;\n};\n\nclass Segtree {\npublic:\n    int n;\n    node* tree;\n\n    Segtree(uint32_t n)\n    {\n        this -> n = n;\n        this -> tree = (node *)calloc(4*n, sizeof(node));\n        this -> build(1, 0, n);\n    }\n\n    node coalesce(node levo, node desno)\n    {\n        node comb;\n        comb.sz = levo.sz + desno.sz;\n        if (levo.sz == levo.big and desno.sz == desno.big)\n        {\n            // both completely empty.\n            comb.big = comb.sz;\n            comb.left = comb.big;\n            comb.right = comb.big;\n        }\n        else if (levo.sz == levo.big)\n        {\n            // left completely empty\n            comb.big = max(desno.big, levo.sz + desno.left);\n            comb.left = levo.sz + desno.left;\n            comb.right = desno.right;\n        }\n        else if (desno.sz == desno.big)\n        {\n            // right completely empty\n            comb.big = max(levo.big, levo.right + desno.sz);\n            comb.right = levo.right + desno.sz;\n            comb.left = levo.left;\n        }\n        else \n        {\n            // both have blocks.\n            comb.big = max(levo.big, levo.right + desno.left);\n            comb.big = max(comb.big, desno.big);\n            comb.left = levo.left;\n            comb.right = desno.right;\n        }\n        return comb;\n    }\n\n    void build(int node, int left, int right)\n    {\n        int sz = right - left + 1;\n        tree[node] = {sz, sz, sz, sz};\n        if (left == right)\n            return;\n        int mid = (left + right)>>1;\n        build(node*2, left, mid);\n        build(node*2+1, mid+1, right);\n    }\n\n    void update(int pos)\n    {\n        __update(1, 0, n, pos);\n    }\n\n    void printnode(node a)\n    {\n        cout<<a.sz<<" "<<a.big<<" "<<a.left<<" "<<a.right<<"\\n";\n    }\n    void __update(int node, int left, int right, int pos)\n    {\n        if (left > right or  pos < left or pos > right)\n            return ;\n        if (left == right)\n        {\n            tree[node] = {1, 0, 0, 0};\n            return ;\n        }\n        int mid = (left + right)>>1;\n        __update(node*2, left, mid, pos);\n        __update(node*2+1, mid + 1, right, pos);\n        tree[node] = coalesce(tree[node*2], tree[node*2+1]);\n    }\n\n    int query(int lrange, int rrange)\n    {\n        vector <node> temp;\n        __query(1, 0, n, temp, lrange, rrange);\n        node cur = {0, 0, 0, 0};\n        for (auto thing : temp)\n        {\n            cur = coalesce(cur, thing);\n        }\n        return cur.big;\n    }\n\n    void __query(int node, int left, int right, vector <struct node> &temp, int lrange, int rrange)\n    {\n        if (left > right or left > rrange or right < lrange)\n            return;\n        if (left >= lrange and right <= rrange)\n        {\n            temp.push_back(tree[node]);\n            return ;\n        }\n        int mid = (left + right)>>1;\n        __query(node*2, left, mid, temp, lrange, rrange);\n        __query(node*2 + 1, mid + 1, right, temp, lrange, rrange);\n    }\n\n};\n\nclass Solution {\npublic:\n    vector<bool> getResults(vector<vector<int>>& queries) {\n        Segtree object(queries.size() * 3 + 1);\n        vector <bool> results;\n        for (vector <int> & query : queries)\n        {\n            if (query[0] == 1)\n            {\n                object.update(query[1]);\n            }\n            else \n            {\n                int x = query[1];\n                int sz = query[2];\n                results.push_back(object.query(1, x-1) + 1 >= sz);\n            }\n        }\n        return results;\n    }\n};\n```
['C++']