数据结构 Trick 之：前缀最大值计数

能够解决的问题

区间前缀最大值计数，单点修，可强制在线。

优缺点

代码好写，但是正常情况下没有吉司机线段树快。

思路

首先，这是一个区间问题，所以我们考虑线段树求解。

我们令一个节点表示他所统辖的区间的答案。那么问题就变成了：如何合并两个区间（也就是说如何写 pushup）？

我们让每个端点再维护一个区间最大值，然后写一个

pu_{u,k}

函数来求

u

节点代表的区间中大于

k

的前缀最大值个数，那么我们只需要这样写

\text{pushup}

：

CPP

void pushup(int u) {
    node[u].v = node[u << 1].v + pu(u << 1 | 1, node[u << 1].maxx);
    node[u].maxx = max(node[u << 1].maxx, node[u << 1 | 1].maxx);
    return ;
}

那么

\text{pu}

函数怎么写呢？

首先，

O(1)

肯定是不行的。我们考虑

O(\log n)

递归：

如果 $maxx_{node_{u << 1}} > k$ ，那么我们发现这个 $k$ 对右半边没有影响，所以只需要递归左半边。
如果 $maxx_{node_{u << 1}} \le k$ ，那么左半边的答案就是 $0$ ，只需要递归右半边。

那么这个函数就

O(\log n)

解决了。

例题与代码

P4198 楼房重建

这道题就是板子，只需要注意一下浮点数运算就行了。

CPP

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define midd ((node[u].l + node[u].r) >> 1)
constexpr int maxn = 100010;
constexpr double eps = 1e-12;

double h[maxn];
int n, m, x, y;

struct segnode {
	int v, l, r;
	double maxx;
} ;
struct segtree {
	segnode node[maxn << 3];
	void build(int u, int l, int r) {
		node[u] = {0, l, r, 0};
		if (l == r) return ;
		build(u << 1, l, midd);
		build(u << 1 | 1, midd + 1, r);
		return ;
	}
	int pu(int u, double k) {
		int ress;
		if (node[u].l == node[u].r) {
			ress = node[u].maxx > k + eps;
			return ress;
		}
		if (node[u << 1].maxx > k + eps) {
			ress = pu(u << 1, k) + node[u].v - node[u << 1].v;
		} else {
			ress = pu(u << 1 | 1, k);
		}
		return ress;
	}
	void pushup(int u) {
		node[u].v = node[u << 1].v + pu(u << 1 | 1, node[u << 1].maxx);
		node[u].maxx = max(node[u << 1].maxx, node[u << 1 | 1].maxx);
		return ;
	}
	void update(int u, int x, double k) {
		if (node[u].l == node[u].r) {
			node[u].maxx = k;
			node[u].v = 1;
			return ;
		}
		if (x <= midd) update(u << 1, x, k);
		else update(u << 1 | 1, x, k);
		pushup(u);
		return ;
	}
} t;

signed main() {
	ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
	
	cin >> n >> m;
	t.build(1, 1, n);
	for (int i = 1; i <= m; i++) {
		cin >> x >> y;
		t.update(1, x, (y * 1.0 / x)); // 一定注意是 y * 1.0 / x, y / x * 1.0 是错的！
		cout << t.node[1].v << '\n';
	}
	
	return 0;
}

数据结构 Trick 之：前缀最大值计数

文章操作

能够解决的问题

优缺点

思路

例题与代码

相关推荐

评论

数据结构 Trick 之：前缀最大值计数