2940.
昨天写不出来
今天边写边吐
想这个树怎么建想好久
宝可梦直接+20胜==
动态开点MLE
看hint不知道怎么用BIT建
改smart pointer还是MLE
最后改成先离散化再开点才过的
要离散化的话
应该不要动态开点更快ㄅ
但是我腿了：（
class Solution {
public:
// segment tree
class Node{
public:
int idx;
Node *l, *r;
Node(){
idx = INT_MAX;
l = nullptr;
r = nullptr;
};
Node(int i){
idx = i;
l = nullptr;
r = nullptr;
};
};
class Segment_tree{
public:
Node* root;
int idx;
Segment_tree(){
root = new Node();
idx = INT_MAX;
}
Segment_tree(int i){
root = new Node(i);
idx = i;
}
void update(Node* nd, int& val, int& idx, int tl = 0, int tr = 1e9){
if(val < tl || tr < val) return;
if(val == tl ){
nd->idx = idx;
}
else{
int mid = (tl + tr) / 2;
if(nd->l == nullptr){
nd->l = new Node();
}
if(nd->r == nullptr){
nd->r = new Node();
}
update(nd->l, val, idx, tl, mid);
update(nd->r, val, idx, mid+1, tr);
nd->idx = min(nd->l->idx, nd->r->idx);
}
}
int query(Node* nd, int& val, int tl = 0, int tr = 1e9){
// (val, inf]
if(nd == nullptr or tr <= val) return INT_MAX;
int idx = INT_MAX;
if(val < tl){
idx = min(idx, nd->idx);
}
else{
int mid = (tl + tr) / 2;
idx = min(idx, query(nd->l, val, tl, mid));
idx = min(idx, query(nd->r, val, mid+1, tr));
}
return idx;
}
};
vector<int> leftmostBuildingQueries(vector<int>& H, vector<vector<int>>& Q) {
// range: val [1, 1e9]
// get min idx
Segment_tree tree;
int n = H.size(), m = Q.size();
// seperate H
vector<int> sp(n);
for(int i = 0; i < n; i++){
sp[i] = i;
}
ranges::sort(sp, [&](int& a, int& b){return H[a] < H[b]; });
int cur = -1, cnt = 0;
for(int& i: sp){
if(H[i] == cur) H[i] = cnt;
else{
cur = H[i];
cnt++;
H[i] = cnt;
}
}
int mx = cnt * 4;
vector<int> order(m), res(m, -1);
// Q[i][1] order
for(int i = 0; i < m; i++){
if(Q[i][0] > Q[i][1]) swap(Q[i][0], Q[i][1]);
order[i] = i;
}
ranges::sort(order, [&](int& a, int& b){ return Q[a][1] < Q[b][1]; });
for(int i = n-1, oi = m-1; i >= 0, oi >= 0; i