https://leetcode.cn/problems/block-placement-queries/description/
有一条无限长的数轴，原点在 0 处，沿着 x 轴 正 方向无限延伸。
给你一个二维数组 queries ，它包含两种操作：
操作类型 1 ：queries[i] = [1, x] 。在距离原点 x 处建一个障碍物。数据保证当操作执行的时候，位置 x 处 没有 任何障碍物。
操作类型 2 ：queries[i] = [2, x, sz] 。判断在数轴范围 [0, x] 内是否可以放置一个长度为 sz 的物块，这个物块需要 完全 放置在范围 [0, x] 内。
如果物块与任何障碍物有重合，那么这个物块 不能 被放置，但物块可以与障碍物刚好接触。注意，你只是进行查询，并 不是 真的放置这个物块。
每个查询都是相互独立的。
请你返回一个 boolean 数组results ，如果第 i 个操作类型 2 的操作你可以放置物块，那么 results[i] 为 true ，否则为 false 。
示例 1：
输入：queries = [[1,2],[2,3,3],[2,3,1],[2,2,2]]
输出：[false,true,true]
解释：
查询 0 ，在 x = 2 处放置一个障碍物。在 x = 3 之前任何大小不超过 2 的物块都可以被放置。
示例 2：
输入：queries = [[1,7],[2,7,6],[1,2],[2,7,5],[2,7,6]]
输出：[true,true,false]
解释：
查询 0 在 x = 7 处放置一个障碍物。在 x = 7 之前任何大小不超过 7 的物块都可以被放置。
查询 2 在 x = 2 处放置一个障碍物。现在，在 x = 7 之前任何大小不超过 5 的物块可以被放置，x = 2 之前任何大小不超过 2 的物块可以被放置。
提示：
1 <= queries.length <= 15 * 104
2 <= queries[i].length <= 3
1 <= queries[i][0] <= 2
1 <= x, sz <= min(5 * 104, 3 * queries.length)
输入保证操作 1 中，x 处不会有障碍物。
输入保证至少有一个操作类型 2 。
线段树记录每个区间的情况，更新某个区间的状态是从他的左右子区间更新
稍有不同的是 子区间l r 表示的是l的前一段区间和到r的位置的 最长连续区间长度和 前缀区间长度和后缀区间长度
那么合并该子区间后，最长区间长度有可能左子区间的前缀 肯能是右子区间的后缀，也可能是左右子区间其中最长连续区间的某一个，
也可能是左区间的后缀加上右区间的前缀。 注意，我的数据结构设计下，
要额外取查看左子区间是否放置了障碍物，才能决定能否合并左区间的后缀和右区间的前缀.
#include <iostream>
#include <vector>
#include <set>
using namespace std;
//https://leetcode.cn/problems/block-placement-queries/description/
class Solution {
public:
const int N = 5 * 10000 + 10;
struct Node
{
int l, r;
int pre, suf, maxv;
}tr[(5 * 10000 + 10) * 4];
set<int> ss;
void pushup(Node& u, Node& l, Node& r)
{
u.maxv = 0; u.suf = 0; u.pre = 0;
u.pre = max(u.pre, l.pre);
if (l.pre == l.r - l.l + 1 && ss.count(l.r) ==0) {
u.pre = max(u.pre, l.pre + r.pre);
}
u.suf = max(u.suf, r.suf);
if (r.suf == r.r - r.l + 1) {
u.suf = max(u.suf, l.suf + r.suf);
}
u.maxv = max(u.maxv, l.maxv);
u.maxv = max(u.maxv, r.maxv);
u.maxv = max(u.maxv, l.suf + r.pre);
}
void pushup(int u)
{
pushup(tr[u], tr[u << 1], tr[u << 1 | 1]);
}
void build(int u, int l, int r) {
if (l == r)
tr[u] = { l, r, 1, 1,1 };
else {
tr[u] = { l, r };
int mid = l + r >> 1;
build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
pushup(u);
}
}
void modify(int u, int x) {
if (tr[u].l == x && tr[u].r == x) {
tr[u] = { tr[u].l,tr[u].r, 1, 0, 1 };
}
else {
int mid = tr[u].l + tr[u].r >> 1;
if (x <= mid) modify(u << 1, x);
else modify(u << 1 | 1, x);
pushup(u);
}
}
Node query(int u, int l, int r) {
if (tr[u].l >= l && tr[u].r <= r) {
return tr[u];
}
else {
int mid = tr[u].l + tr[u].r >> 1;
if (r <= mid) return query(u << 1, l, r);
else if (l > mid) return query(u << 1 | 1, l, r);
else
{
auto left = query(u << 1, l, r);
auto right = query(u << 1 | 1, l, r);
Node res; memset(&res, 0, sizeof res);
pushup(res, left, right);
return res;
}
}
}
vector<bool> getResults(vector<vector<int>>& queries) {
vector<bool> ans;
build(1, 1, N);
for (auto e : queries) {
if (e[0] == 1) {
int m = e[1];
ss.insert(m);
modify(1, m);
}
else {
int r = e[1]; int x = e[2];
auto ret = query(1, 1, r);
if (ret.maxv >= x) {
ans.push_back(true);
}
else {
ans.push_back(false);
}
}
}
return ans;
}
};
int main()
{
Solution s;
//vector<vector<int>> v{ {1,2},{2,3,3},{2,3,1},{2,2,2} };
//vector<vector<int>> v{ {1,7},{2,7,6},{1,2},{2,7,5},{2,7,6} };
vector<vector<int>> v{ {2,1,6},{1,4},{2,7,5} };
s.getResults(v);
}