楼房重建线段树

Svemit / 2024-02-07 / 原文

维护前缀最大值个数。

对 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;
}