※ 引述《JIWP (神楽めあ的錢包)》之銘言：
: 3479. Fruits Into Baskets III
昨天那題我沒寫
這題看完沒什麼想法
區間最大 區間修改
懶得思考就線段樹吧==
不過這題才medium
不知道有沒有更簡單的解法
單調什麼之類的
看其他人也是用線段樹
class Solution {
public:
int numOfUnplacedFruits(vector<int>& fruits, vector<int>& baskets) {
int n = fruits.size();
int sz = n * 4 + 1;
vector<int> tree(sz, 0); // segment_tree for baskets
// [1, n] 1-indexed
init(tree, 1, 1, n, baskets);
int res = 0;
for(int i: fruits){
//cout << i << '\n';
if(tree[1] < i) res++;
else update(tree, 1, 1, n, i);
}
return res;
}
void update(vector<int>& tree, int idx, int l, int r, int i){
if(l == r){
tree[idx] = 0;
return;
}
//cout << idx << ' ' << l << " " << r << '\n';
int m = l + (r - l) / 2;
if(tree[idx*2] >= i){ // leftest
update(tree, idx*2, l, m, i);
}
else{
update(tree, idx*2 + 1, m + 1, r, i);
}
tree[idx] = max(tree[idx*2], tree[idx*2 + 1]);
}
void init(vector<int>& tree, int idx, int l, int r, vector<int>& baskets){
if(l == r){
tree[idx] = baskets[l-1]; // 0-indexed
return;
}
int m = l + (r - l) / 2;
init(tree, idx*2, l, m, baskets);
init(tree, idx*2 + 1, m+1, r, baskets);
tree[idx] = max(tree[idx*2], tree[idx*2 + 1]);
}
};

大師