Re: [閒聊] 每日leetcode
複習
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]--;
}
int mx = 0, cur = 0;
for(int& cnt: mp){
cur += cnt;
mx = max(mx, cur);
}
return mx;
}
};
※ 引述《sixB (6B)》之銘言：
: 2779.
: 就是meeting room
: 開map好慢==
: 改array快多ㄌ
: 我還是很不會寫線段樹
: 為啥之前寫了一個lazy不用下傳的
: 很神奇==
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 123.205.121.194 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1733886644.A.859.html
→
12/11 11:11,
1年前
, 1F
12/11 11:11, 1F
推
12/11 11:12,
1年前
, 2F
12/11 11:12, 2F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 1195 之 1554 篇)：