※ 引述《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]);
}
};

大师