offline + max segmen tree | c++
Intuition\nsorry for my weird val name\n\n# Code\n\ntypedef long long ll;\n\nclass Solution {\npublic:\n\n    const ll inf = 1e18;\n    \n    ll block[50005], p
# Intuition\nsorry for my weird val name\n\n# Code\n```\ntypedef long long ll;\n\nclass Solution {\npublic:\n\n    const ll inf = 1e18;\n    \n    ll block[50005], parent[50005], cost[50005];\n    \n    vector<ll> seg;\n\n    void upd(ll node, ll l, ll r, ll idx, ll val) {\n        if (idx < l || idx > r) {\n            return;\n        }\n        if (l >= r) {\n            if (l == idx) {\n                seg[node] = val;\n            }\n            return;\n        }\n        ll mid = l + (r - l) / 2;\n        ll l_node = 2 * node + 1;\n        ll r_node = 2 * node + 2;\n        upd(l_node, l, mid, idx, val), upd(r_node, mid + 1, r, idx, val);\n        seg[node] = max(seg[l_node], seg[r_node]);\n    }\n\n    ll query(ll node, ll l, ll r, ll l_query, ll r_query) {\n        if (l_query <= l && r_query >= r) {\n            return seg[node];\n        }\n        if (l_query > r || r_query < l) {\n            return -inf;\n        }\n        ll mid = l + (r - l) / 2;\n        ll l_node = 2 * node + 1;\n        ll r_node = 2 * node + 2;\n        return max(query(l_node, l, mid, l_query, r_query), query(r_node, mid + 1, r, l_query, r_query));\n    }\n    \n    int root(int p) {\n        return (p == parent[p] ? p : parent[p] = root(parent[p]));\n    }\n    \n    vector<bool> getResults(vector<vector<int>>& queries) {\n        ios_base::sync_with_stdio(0);\n        cin.tie(0);\n\n        const ll n = 50000; // max index\n\n        seg.resize(4 * n, 0);\n        for (auto e : queries) {\n            if (e[0] == 1) {\n                int x = e[1];\n                block[x] = 1;\n            }\n        }\n        block[n] = 1; // last segment\n        int par = 0, cnt = 0;\n        for (int i = 1; i <= n; i++) {\n            parent[i] = par;\n            cnt++;\n            if (block[i]) {\n                cost[par] = cnt;\n                upd(0, 0, n - 1, par, cost[par]);\n                cnt = 0;\n                par = i + 1;\n            }\n        }\n        reverse(queries.begin(), queries.end());\n        vector<bool> ans;\n        for (auto e : queries) {\n            if (e[0] == 1) {\n                int x = e[1];\n                int u = root(x), v = root(x + 1);\n                if (u == v) {\n                    continue;\n                }\n                parent[v] = u;\n                cost[u] += cost[v];\n                upd(0, 0, n - 1, u, cost[u]);\n            }\n            else {\n                int x = e[1], sz = e[2];\n                int v = root(x);\n                upd(0, 0, n - 1, v, x - max(0, v - 1)); // last segment reach most x\n                int val = query(0, 0, n - 1, 0, v);\n                upd(0, 0, n - 1, v, cost[v]);\n                ans.push_back(val >= sz);\n            }\n        }\n        reverse(ans.begin(), ans.end());\n        return ans;\n    }\n};\n```
['Union Find', 'Segment Tree', 'C++']