type seg []int
// 把 i 处的值改成 val
func (t seg) update(o, l, r, i, val int) {
if l == r {
t[o] = val
return
}
m := (l + r) >> 1
if i <= m {
t.update(o<<1, l, m, i, val)
} else {
t.update(o<<1|1, m+1, r, i, val)
}
t[o] = max(t[o<<1], t[o<<1|1])
}
// 查询 [0,R] 中的最大值
func (t seg) query(o, l, r, R int) int {
if r <= R {
return t[o]
}
m := (l + r) >> 1
if R <= m {
return t.query(o<<1, l, m, R)
}
return max(t[o<<1], t.query(o<<1|1, m+1, r, R))
}
func getResults(queries [][]int) (ans []bool) {
m := 0
for _, q := range queries {
m = max(m, q[1])
}
m++
set := redblacktree.New[int, struct{}]()
set.Put(0, struct{}{}) // 哨兵
set.Put(m, struct{}{})
t := make(seg, 2<<bits.Len(uint(m)))
for _, q := range queries {
x := q[1]
if q[0] == 1 {
pre, _ := set.Floor(x) // x 左侧最近障碍物的位置
nxt, _ := set.Ceiling(x) // x 右侧最近障碍物的位置
set.Put(x, struct{}{})
t.update(1, 0, m, x, x-pre.Key) // 更新 d[x] = x - pre
t.update(1, 0, m, nxt.Key, nxt.Key-x) // 更新 d[nxt] = nxt - x
} else {
pre, _ := set.Floor(x - 1) // x 左侧最近障碍物的位置
// 最大长度要么是 [0,pre] 中的最大 d，要么是 [pre,x] 这一段的长度
maxGap := max(t.query(1, 0, m, pre.Key), x-pre.Key)
ans = append(ans, maxGap >= q[2])
}
}
return
}
class Solution {
public List<Boolean> getResults(int[][] queries) {
int m = 0;
for (int[] q : queries) {
m = Math.max(m, q[1]);
}
m++;
TreeSet<Integer> set = new TreeSet<>(List.of(0, m)); // 哨兵
int[] t = new int[2 << (32 - Integer.numberOfLeadingZeros(m))];
List<Boolean> ans = new ArrayList<>();
for (int[] q : queries) {
int x = q[1];
if (q[0] == 1) {
int pre = set.floor(x); // x 左侧最近障碍物的位置
int nxt = set.ceiling(x); // x 右侧最近障碍物的位置
set.add(x);
update(t, 1, 0, m, x, x - pre); // 更新 d[x] = x - pre
update(t, 1, 0, m, nxt, nxt - x); // 更新 d[nxt] = nxt - x
} else {
int pre = set.floor(x - 1); // x 左侧最近障碍物的位置
// 最大长度要么是 [0,pre] 中的最大 d，要么是 [pre,x] 这一段的长度
int maxGap = Math.max(query(t, 1, 0, m, pre), x - pre);
ans.add(maxGap >= q[2]);
}
}
return ans;
}
// 把 i 处的值改成 val
private void update(int[] t, int o, int l, int r, int i, int val) {
if (l == r) {
t[o] = val;
return;
}
int m = (l + r) / 2;
if (i <= m) {
update(t, o * 2, l, m, i, val);
} else {
update(t, o * 2 + 1, m + 1, r, i, val);
}
t[o] = Math.max(t[o * 2], t[o * 2 + 1]);
}
// 查询 [0,R] 中的最大值
private int query(int[] t, int o, int l, int r, int R) {
if (r <= R) {
return t[o];
}
int m = (l + r) / 2;
if (R <= m) {
return query(t, o * 2, l, m, R);
}
return Math.max(t[o * 2], query(t, o * 2 + 1, m + 1, r, R));
}
}
class Solution {
vector<int> t;
// 把 i 处的值改成 val
void update(int o, int l, int r, int i, int val) {
if (l == r) {
t[o] = val;
return;
}
int m = (l + r) / 2;
if (i <= m) {
update(o * 2, l, m, i, val);
} else {
update(o * 2 + 1, m + 1, r, i, val);
}
t[o] = max(t[o * 2], t[o * 2 + 1]);
}
// 查询 [0,R] 中的最大值
int query(int o, int l, int r, int R) {
if (r <= R) {
return t[o];
}
int m = (l + r) / 2;
if (R <= m) {
return query(o * 2, l, m, R);
}
return max(t[o * 2], query(o * 2 + 1, m + 1, r, R));
}
public:
vector<bool> getResults(vector<vector<int>>& queries) {
int m = 0;
for (auto& q : queries) {
m = max(m, q[1]);
}
m++;
set<int> st{0, m}; // 哨兵
t.resize(2 << (32 - __builtin_clz(m)));
vector<bool> ans;
for (auto& q : queries) {
int x = q[1];
auto it = st.lower_bound(x);
int pre = *prev(it); // x 左侧最近障碍物的位置
if (q[0] == 1) {
int nxt = *it; // x 右侧最近障碍物的位置
st.insert(x);
update(1, 0, m, x, x - pre); // 更新 d[x] = x - pre
update(1, 0, m, nxt, nxt - x); // 更新 d[nxt] = nxt - x
} else {
// 最大长度要么是 [0,pre] 中的最大 d，要么是 [pre,x] 这一段的长度
int max_gap = max(query(1, 0, m, pre), x - pre);
ans.push_back(max_gap >= q[2]);
}
}
return ans;
}
};
