维护前缀最大值个数。
对 pushup
操作进行修改。
定义 solve(x, lim)
为前面这个区间的最大值为 lim
,\(x\) 支配的区间产生的贡献。
如果 \(x\) 的最大值已经小于 \(lim\),显然没有贡献。
考虑 \(x\) 的左儿子,如果左儿子的最大值大于 \(lim\) 直接递归左二子查询,此时右儿子的答案不受影响。
如果左儿子最大值小于 \(lim\) 的话,贡献显然为0,递归右儿子查询。
\(solve\) 每次只会递归一个儿子,一共 \(O(\log n)\) 层,复杂度 \(O(\log n)\)。
总复杂度 \(O(n\log ^ 2 n)\)。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5 + 5, INF = 0x3f3f3f3f;
const LL mod = 998244353;
int n, m;
struct Segment_Tree {
struct Node {
int l, r, val;
double maxv;
#define l(x) tr[x].l
#define r(x) tr[x].r
#define val(x) tr[x].val
#define mx(x) tr[x].maxv
} tr[N << 2];
void build(int l, int r, int x) {
tr[x] = {l, r};
if (l == r) return;
int mid = (l + r) / 2;
build(l, mid, x * 2), build(mid + 1, r, x * 2 + 1);
}
int solve(int x, double lim) {
if (mx(x) <= lim) return 0;
if (l(x) == r(x)) return 1;
if (mx(x * 2) <= lim) return solve(x * 2 + 1, lim);
else return solve(x * 2, lim) + val(x) - val(x * 2);
}
void pushup(int x) {
mx(x) = max(mx(x * 2), mx(x * 2 + 1));
val(x) = val(x * 2) + solve(x * 2 + 1, mx(x * 2));
}
void update(int p, int x, double v) {
if (l(x) == r(x)) {
mx(x) = v;
val(x) = 1;
return;
}
int mid = (l(x) + r(x)) / 2;
if (p <= mid) update(p, x * 2, v);
else update(p, x * 2 + 1, v);
pushup(x);
}
} SegT;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
cin >> n >> m;
SegT.build(1, n, 1);
for (int i = 1; i <= m; i ++) {
int x, y;
cin >> x >> y;
SegT.update(x, 1, (double)y / x);
cout << SegT.val(1) << '\n';
}
return 0;
}
标签:val,int,楼房,线段,tr,lim,define,最大值,重建
From: https://www.cnblogs.com/Svemit/p/18010738