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

porse · 2025-01-19 16:10:07 · 算法·理论

能够解决的问题

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

优缺点

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

思路

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

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

我们让每个端点再维护一个区间最大值，然后写一个 pu_{u,k} 函数来求 u 节点代表的区间中大于 k 的前缀最大值个数，那么我们只需要这样写 \text{pushup}：

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 楼房重建

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

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