Implicit treap
Intuition\nLet\'s try simulating the problem. We\'ll keep an array of segments. At first, it\'s going to contain a single large segment, e.g. [1e9=INF]. After p
# Intuition\nLet\'s try simulating the problem. We\'ll keep an array of segments. At first, it\'s going to contain a single large segment, e.g. `[1e9=INF]`. After placing a barrier at `x=7`, we\'ll change it to `[7,INF]` (actually, we\'ll store `[7,INF-7]` but it doesn\'t matter). When we add a barrier at `x=2`, the array will become `[2,5,INF]`.\nLet\'s try to answer our two queries:\n1. Adding a new barrier. We can "binsearch" for our position if we have an efficient way to store prefix sums (e.g. `arr=[2,5,INF], sums=[2,7,INF]`, we want to add a new barrier at `x=6`. Let\'s find the first prefix sum larger than `6`, which is `sums[1]=7` and split this element into two `7-6=1` and `6-2=4`, making our resulting array `[2,4,1,INF]`).\n2. Finding out if there\'s a block that fits. Once again, we can binsearch for `x` to find out where our right side is, then we\'ll need to find the maximum on the array.\ne.g. `arr=[2,5,INF], sums=[2,7,INF], x=10`. The first sum that\'s larger than `10` is `INF`, meaning we can choose between the prefix `[2,5]` and `10-7=3` (last \'block\' is processed separately).\n\nNow we have to do these queries efficiently. For this, we\'ll use a treap. \n\n# Approach\n(read [Article](https://cp-algorithms.com/data_structures/treap.html) for more information). Essentially, a treap is a balanced (if we use random priorities) binary search tree that we can split and merge in $$O(logn)$$.\nAn implicit treap is a treap based on an array where the tree keys are array indexes. This essentially gives us an \'array\' data structure that supports the following operations:\n1. Insertion of one element or multiple consecutive elements in $$O(logn)$$.\n2. Deleting an element or multiple consecutive elements in $$O(logn)$$.\n3. Computing any range operation (e.g. max or sum on any subarray) in $$O(logn)$$.\n\nWe\'ll use this to solve our problem.\nLet\'s see how we can add a barrier. We\'ll do a binseach in $$O(logn)$$ by storing the sums of nodes and choosing the right direction (this is essentialy a problem \'find a node in a binary tree such that all the elements smaller than it have a sum of X\'). Then, we\'re just removing one element and adding two, which is once again $$O(log n)$$.\nA check is done similarly. Here, we\'ll also need to store maximum for each subtree together with the sum. We binsearch, split the tree to find the maximum, do our check and merge the tree back again, all in $$O(logn)$$\n\n# Complexity\n- Time complexity: $$O(qlogq)$$\n\n# Code\n```\n#include <iostream>\n#include <utility>\n#include <vector>\n#include <algorithm>\n#include <numeric>\n#include <map>\n#include <unordered_set>\n#include <iostream>\n#include <utility>\n#include <vector>\n#include <algorithm>\n#include <numeric>\n#include <map>\n#include <unordered_set>\n#include <unordered_map>\n#include <queue>\n#include <set>\n#include <stack>\n#include <fstream>\n#include <ext/pb_ds/assoc_container.hpp>\n#include <ext/pb_ds/tree_policy.hpp>\n#include <bitset>\n#include <sstream>\n#include <ext/rope>\n#include <ctime>\n#include <random>\n#include <cstdlib>\n#include <complex>\n\nusing namespace std;\nusing namespace __gnu_pbds;\nusing namespace __gnu_cxx;\n\n/* clang-format off */\n\n/* TYPES  */\n#define ll long long\n#define pii pair<int, int>\n#define pll pair<long long, long long>\n#define vi vector<int>\n#define vll vector<long long>\n#define vpii vector<pair<int, int>>\n#define vpii vector<pair<int, int>>\n#define vvpii vector<vector<pair<int, int>>>\n#define vpll vector<pair<long long, long long>>\n#define vvpll vector<vector<pair<long long, long long>>>\n#define vvi vector<vector<int>>\n#define vvll vector<vector<long long>>\n#define mii map<int, int>\n#define si set<int>\n#define sc set<char>\n\n\n\n/* FUNCTIONS */\n#define feach(el, v) for(auto &el: v)\n#define rep(i, n) for(int i=0;i<n;i++)\n#define reprv(i, n) for(int i=n-1;i>=0;i--)\n#define reps(i, s, e) for(int i=s;i<e;i++)\n#define reprve(i, e, s) for(int i=e;i>=s;i--)\n#define repe(x, y) for (auto &x: y)\n#define repe2(x, a, y) for (auto &[x,a]: y)\n\ntypedef tree<int, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update> oSet;\n\n\nstruct treap {\n    struct item {\n        int prior, value, cnt, sum, max;\n        item *l, *r;\n    };\n\n    item *root{nullptr};\n\n    auto getRng() -> int { return (rand() << 16) ^ rand(); }\n\n    int cnt(item *it) { return it ? it->cnt : 0; }\n    int sumV(item *it) { return it ? it->sum : 0; }\n    int maxV(item *it) { return it ? it -> max : 0; }\n\n    void updAll(item *it) {\n        if (it) {\n            it->cnt = cnt(it->l) + cnt(it->r) + 1;\n            it-> max = max(max(maxV(it->l), maxV(it->r)), it->value);\n            it-> sum = sumV(it->l) + sumV(it->r) + it->value;\n        }\n    }\n\n    void merge(item *&t, item *l, item *r) {\n        if (!l) t = r;\n        else if (!r) t = l;\n        else if (l->prior > r->prior) merge(l->r, l->r, r), t = l;\n        else merge(r->l, l, r->l), t = r;\n        updAll(t);\n    }\n\n    void split(item *t, item *&l, item *&r, int key, int add = 0) {\n        if (!t) return void(l = r = nullptr);\n\n        int cur_key = add + cnt(t->l);\n        if (key <= cur_key) split(t->l, l, t->l, key, add), r = t;\n        else split(t->r, t->r, r, key, add + 1 + cnt(t->l)), l = t;\n        updAll(t);\n    }\n\n    int getValue(item *t, int pos) {\n        int lCnt = cnt(t->l);\n        if (pos < lCnt) return getValue(t->l, pos);\n        else if (pos == lCnt) return t->value;\n        else return getValue(t->r, pos - lCnt - 1);\n    }\n\n    item* newItem(int val) { return new item{getRng(), val, 1, val, val}; }\n\n    void replace(int pos, int l, int r) {\n        item *t1, *t2, *t3, *t4;\n        split(root, t1, t2, pos);\n        split(t2, t3, t4, 1);\n        item *lI = newItem(l), *rI = newItem(r);\n        merge(root, t1, lI);\n        merge(root, root, rI);\n        merge(root, root, t4);\n    }\n\n    auto operator += (int val) -> void { merge(root, root, newItem(val)); }\n\n    auto operator[](int pos) -> int { return getValue(root, pos); }\n\n    int findMaxRange(int rpos) {\n        item *t1, *t2;\n        split(root, t1, t2, rpos + 1);\n        int ans = maxV(t1);\n        merge(root, t1, t2);\n        return ans;\n    }\n\n    int findSumRange(int rpos) {\n        item *t1, *t2;\n        split(root, t1, t2, rpos + 1);\n        int ans = sumV(t1);\n        merge(root, t1, t2);\n        return ans;\n    }\n\n    int binSearchPos(item* x, int sum, int skip = 0) {\n        int lSum = sumV(x->l), lCnt = cnt(x->l);\n        if (lSum <= sum && lSum + x->value > sum) return skip + lCnt;\n        if (lSum > sum) return binSearchPos(x->l, sum, skip);\n        else return binSearchPos(x->r, sum - lSum - x->value, skip + lCnt + 1);\n    }\n\n    int query(int right) {\n        int bs = binSearchPos(root, right);\n        int left = bs - 1;\n        int maxLeft = (left >= 0 ? findMaxRange(left) : 0);\n        int leftVal = (left >= 0 ? findSumRange(left) : 0);\n        return max(maxLeft, right - leftVal);\n    }\n\n    void insert(int pos) {\n        int bs = binSearchPos(root, pos);\n        int left = bs - 1;\n        int sumLeft = (left >= 0 ? findSumRange(left) : 0);\n        int sumRight = sumLeft + getValue(root, bs);\n        int newL = pos - sumLeft, newR = sumRight - pos;\n        replace(bs, newL, newR);\n    }\n};\n\n\nclass Solution {\npublic:\n    vector<bool> getResults(vector<vector<int>>& queries) {\n        srand((unsigned)time(0));\n        treap t; t += 1e9;\n\n        vector<bool> ans;\n        int n = queries.size();\n        rep(i, n) {\n            int type = queries[i][0];\n            if (type == 1) {\n                t.insert(queries[i][1]);\n            } else {\n                int r = queries[i][1], len = queries[i][2];\n                int currAns = t.query(r);\n                bool check = currAns >= len;\n                ans.push_back(check);\n            }\n        }\n        return ans;\n    }\n};\n\n```
['C++']