【线段树】个人训练-Leetcode-3161. Block Placement Queries

标题链接：https://leetcode.cn/problems/block-placement-queries/description/
标题大意：在x轴上，有两种操纵：

• 在某个点上插入一个停滞物
  
• 查询，在[0, x]区间内，能否放下长度为sz的物品
  

插入和查询操纵瓜代举行，返回每次查询的结果。
思绪：一开始时望见标题写的"anywhere"以为是【区间内每处都能放下物品】，寻思着那不是整个区间都没有停滞物才行吗，似乎判断有点简朴了。厥后才发现只要有一处能放下就行了。
那实在就是查询[0, x]区间内，被停滞物隔开的各个区间中，能存储的最大长度。这种涉及区间查询的，应该用线段树来办理。然而长期不写已经忘了线段树怎么写了…看了很多题解，照旧灵神的比力清楚。
更新i处的值为val

1.         void update(int o, int l, int r, int i, int val) {
2.         if (l == r) {
3.             tree[o] = val;
4.             return;
5.         }
6.         int mid = (l + r) / 2;
7.         if (i <= mid)
8.             update(o * 2, l, mid, i, val);
9.         else
10.             update(o * 2 + 1, mid+1, r, i, val);
11.         tree[o] = max(tree[o * 2], tree[o*2 + 1]);
12.     }

复制代码

返回[0, x]中最大的区间长度

1.         int query(int o, int l, int r, int x) {
2.         if (r <= x)
3.             return tree[o];
4.         int mid = (l + r) / 2;
5.         if (x <= mid)
6.             return query(o * 2, l, mid, x);
7.         return max(tree[o * 2], query(o * 2 + 1, mid + 1, r, x));
8.     }

复制代码

对于[0, x]来说，要么最大长度在[0, pre]（pre是x左边的最大的停滞物位置）之间，要么在[pre, x]之间（由于每个query中x实在也相称于一个暂时的停滞）。
完备代码

1. class Solution {
2. public:
3.     vector<int> tree;
5.     void update(int o, int l, int r, int i, int val) {
6.         if (l == r) {
7.             tree[o] = val;
8.             return;
9.         }
10.         int mid = (l + r) / 2;
11.         if (i <= mid)
12.             update(o * 2, l, mid, i, val);
13.         else
14.             update(o * 2 + 1, mid+1, r, i, val);
15.         tree[o] = max(tree[o * 2], tree[o*2 + 1]);
16.     }
18.     int query(int o, int l, int r, int x) {
19.         if (r <= x)
20.             return tree[o];
21.         int mid = (l + r) / 2;
22.         if (x <= mid)
23.             return query(o * 2, l, mid, x);
24.         return max(tree[o * 2], query(o * 2 + 1, mid + 1, r, x));
25.     }
27.     vector<bool> getResults(vector<vector<int>>& queries) {
28.         int maxn = 0;
29.         for (auto q : queries)
30.             maxn = max(maxn, q[1]);
31.         maxn++;
32.         
33.         set<int> st{0, maxn};
34.         tree.resize(2 << (32 - __builtin_clz(maxn)));
35.         vector<bool> res;
36.         
37.         for (auto q : queries) {
38.             int x = q[1];
39.             auto it = st.lower_bound(x);
40.             int pre = *std::prev(it);
41.             if (q[0] == 1) {
42.                 int nxt = *it;
43.                 st.insert(x);
44.                 update(1, 0, maxn, x, x - pre);
45.                 update(1, 0, maxn, nxt, nxt - x);
46.             }
47.             else {
48.                 int maxlen = max(query(1, 0, maxn, pre), x - pre);
49.                 res.push_back(maxlen >= q[2]);
50.             }
51.         }
52.         return res;
53.     }
54. };

复制代码