複習
lazy不用往下傳
因為都查第一個
不用查lazy下面的
真的很神奇==
class Solution {
public:
vector<int> tree, lz;
int maximumBeauty(vector<int>& nums, int k) {
int sz = 1e5 * 4 + 1;
tree = vector<int>(sz, 0);
lz = tree;
// initial all zero, no need build
for(int& i: nums){
//[i-k, i+k]
// offset k, [i, i+2k]
push(1, i, i + k*2);
}
return tree[1];
}
void push(int nd, int s, int e, int tl = 0, int tr = 1e5){
// out of range
if(e < tl || tr < s) return;
if(s <= tl && tr <= e){
tree[nd]++;
lz[nd]++;
}
else{
int mid = (tl + tr) / 2;
push(nd * 2, s, e, tl, mid);
push(nd * 2 + 1 , s, e, mid+1, tr);
tree[nd] = lz[nd] + max(tree[nd * 2], tree[nd * 2 + 1]);
}
}
};
O(nlogn)真的比 O(n+k)慢1000倍
太科學了
class Solution {
public:
int maximumBeauty(vector<int>& nums, int k) {
int sz = *ranges::max_element(nums);
vector<int> mp(sz + 2*k + 2, 0);
for(int& i: nums){
//[i-k, i+k]
//[i-k, i+k+1)
// offset [i, i+2k+1)
mp[i]++;
mp[i + k*2 + 1]