Re: [閒聊] 每日leetcode

看板Marginalman作者sixB (6B)時間11月前 (2024/12/23 23:26)推噓0(0推 0噓 1→)

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--){ // H: i, order: oi //cout << i << ": \n"; while(oi >= 0 and Q[ order[oi] ][1] >= i){ //cout << oi << " " << Q[ order[oi] ][1] << " "; int &ai = Q[ order[oi] ][0], &bi = Q[ order[oi] ][1]; if(ai == bi or H[ai] < H[bi] ){ res[order[oi]] = bi; //cout << "no q: " << bi << '\n'; } else{ int q = tree.query(tree.root, H[ai], 0, mx); if(q != INT_MAX) res[order[oi]] = q; //cout << "q: " << q << '\n'; } oi--; } tree.update(tree.root, H[i], i, 0, mx); } return res; } }; ※ 引述《dont (dont)》之銘言： : 2940. Find Building Where Alice and Bob Can Meet : ## 思路 ----- Sent from JPTT on my iPad -- 很姆的咪姆之咪 http://i.imgur.com/5sw7QOj.jpg