题目链接：https://leetcode.cn/problems/block-placement-queries/description/
题目大意：在x轴上，有两种操作：
- 在某个点上插入一个障碍物
- 查询，在
[0, x]区间内，能否放下长度为sz的物品
插入和查询操作交替进行，返回每次查询的结果。
思路：一开始时看见题目写的"anywhere"以为是【区间内每处都能放下物品】，寻思着那不是整个区间都没有障碍物才行吗，好像判断有点简单了。后来才发现只要有一处能放下就行了。
那其实就是查询[0, x]区间内，被障碍物隔开的各个区间中，能存储的最大长度。这种涉及区间查询的，应该用线段树来解决。然而长久不写已经忘了线段树怎么写了…看了很多题解，还是灵神的比较清晰。
更新i处的值为val
void update(int o, int l, int r, int i, int val) {if (l == r) {tree[o] = val;return;}int mid = (l + r) / 2;if (i <= mid)update(o * 2, l, mid, i, val);elseupdate(o * 2 + 1, mid+1, r, i, val);tree[o] = max(tree[o * 2], tree[o*2 + 1]);}
返回[0, x]中最大的区间长度
int query(int o, int l, int r, int x) {if (r <= x)return tree[o];int mid = (l + r) / 2;if (x <= mid) return query(o * 2, l, mid, x);return max(tree[o * 2], query(o * 2 + 1, mid + 1, r, x)); }
对于[0, x]来说，要么最大长度在[0, pre]（pre是x左边的最大的障碍物位置）之间，要么在[pre, x]之间（因为每个query中x其实也相当于一个暂时的障碍）。
完整代码
class Solution {
public:vector<int> tree;void update(int o, int l, int r, int i, int val) {if (l == r) {tree[o] = val;return;}int mid = (l + r) / 2;if (i <= mid)update(o * 2, l, mid, i, val);elseupdate(o * 2 + 1, mid+1, r, i, val);tree[o] = max(tree[o * 2], tree[o*2 + 1]);}int query(int o, int l, int r, int x) {if (r <= x)return tree[o];int mid = (l + r) / 2;if (x <= mid) return query(o * 2, l, mid, x);return max(tree[o * 2], query(o * 2 + 1, mid + 1, r, x)); }vector<bool> getResults(vector<vector<int>>& queries) {int maxn = 0;for (auto q : queries)maxn = max(maxn, q[1]);maxn++;set<int> st{0, maxn};tree.resize(2 << (32 - __builtin_clz(maxn)));vector<bool> res;for (auto q : queries) {int x = q[1];auto it = st.lower_bound(x);int pre = *std::prev(it);if (q[0] == 1) {int nxt = *it;st.insert(x);update(1, 0, maxn, x, x - pre);update(1, 0, maxn, nxt, nxt - x);}else {int maxlen = max(query(1, 0, maxn, pre), x - pre);res.push_back(maxlen >= q[2]);}}return res;}
};
