Square Root Decomposition.
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```\nstruct node\n{\n    int sz;\n    int big;\n    int left;\n    int right;\n};\n\nclass Blocks {\npublic:\n    int n;\n    bool* arr;\n    int chunksize;\n    node* blocks;\n\n    Blocks(uint32_t n)\n    {\n        this -> n = n;\n        this -> chunksize = sqrt(n)+1;\n        this -> arr = (bool *) calloc(n + 3 + chunksize, sizeof(bool));\n        this -> blocks = (node *)malloc((chunksize+2)*sizeof(node));\n        for (int it = 0, at = 0; at <= n; it++, at += chunksize)\n            blocks[it] = {chunksize, chunksize, chunksize, chunksize};\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    node compute(int left, int right)\n    {\n        int st = left;\n        while (!arr[st] and st < right)\n            st++;\n\n        int end = right;\n        while (end >= 0 and !arr[end])\n            end--;\n\n        node block;\n        block.sz = right - left + 1;\n        block.left = st - left;\n        block.right = right - end;\n        int cons = 0;\n        int mx = 0;\n        for (int i = left; i <= right; i++)\n        {\n            if (!arr[i])\n                mx = max(mx, ++cons);\n            else\n                cons = 0;\n        }\n        block.big = mx;\n        return block;\n    }\n\n    void update(int pos)\n    {\n        arr[pos] = 1;\n        int it = 0, at = 0;\n        while (at <= n)\n        {\n            if (at <= pos and pos < at + chunksize)\n            {\n                blocks[it] = compute(at, at + chunksize - 1);\n                break;\n            }\n            it++;\n            at += chunksize;\n        }\n    }\n\n    int query(int lrange, int rrange)\n    {\n        if (rrange - lrange <= chunksize)\n        {\n            node cur = compute(lrange, rrange);\n            return cur.big;\n        }\n\n        int it = 0, at = 0;\n        node cur = {0, 0, 0, 0};\n        while (at <= rrange)\n        {\n            if (lrange <= at and at + chunksize - 1 <= rrange) // entirely inside.\n                cur = coalesce(cur, blocks[it]); \n            else if (at < lrange and lrange < at + chunksize) // leftmost block partly inside.\n                cur = coalesce(cur, compute(lrange, at + chunksize - 1));\n            else if (at <= rrange and rrange < at + chunksize - 1)  // rightmost block partly inside.\n                cur = coalesce(cur, compute(at, rrange));\n            it++;\n            at += chunksize;\n        }\n        return cur.big;\n    }\n\n    void printblock (node block)\n    {\n        cout<<block.sz<<" "<<block.big<<" "<<block.left<<" "<<block.right<<"\\n";\n    }\n\n};\n\nclass Solution {\npublic:\n    vector<bool> getResults(vector<vector<int>>& queries) {\n        Blocks 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++']