Luogu P4198 楼房重建

题目描述

https://www.luogu.com.cn/problem/P4198

简要题意：给定一个长度为 $n$ 的序列 $a$ 和 $m$ 次操作，初始时 $a_i$ 都等于 $0$，每次操作首先修改 $a_x$ 为 $y$，然后查询整个序列的前缀最大值的个数

$n,m\le 10^5$

Solution

我们考虑使用线段树来维护这个东西，定义 $calc(i,l,r,p)$ 表示对于线段树上的节点 $i$，其所代表的区间为 $[l,r]$，在遍历这个区间之前的最大值为 $a[p]$，遍历这个区间后答案会增加多少

我们考虑如何计算这个东西，如果 $[l,m]$ 中的最大值大于 $a[p]$，那么答案就是 $calc(lc,l,m,p)+calc(rc,m+1,r,p_{lc})$，否则答案就是 $calc(rc,m+1,r,p)$，我们对于线段树上每个节点存储最大值的位置 $p$ 和 $calc(rc,m+1,r,p_{lc})$​

因为 $calc$ 的计算是 $O(\log n)$，所以单点修改和查询都是 $O(n\log^2 n)$​ 的

注意这道题是可以做到区间查询的

#include <iostream>
#include <algorithm>
#include <vector>
#define maxn 100010
#define INF 1000000000
using namespace std;

int n, m;
double a[maxn];

#define lc (i << 1)
#define rc (i << 1 | 1)
struct Seg {
    int p;
    pair<int, int> v;
} T[maxn * 4];
pair<int, int> calc(int i, int l, int r, int p) {
    if (a[T[i].p] <= a[p]) return make_pair(0, p);
    if (l == r) return make_pair(1, l);
    int m = l + r >> 1;
    if (a[T[lc].p] > a[p]) return make_pair(calc(lc, l, m, p).first + T[i].v.first, T[i].v.second);
    else return calc(rc, m + 1, r, p); 
}

inline void maintain(int i, int l, int r) {
    T[i].p = a[T[lc].p] >= a[T[rc].p] ? T[lc].p : T[rc].p;
    int m = l + r >> 1;
    T[i].v = calc(rc, m + 1, r, T[lc].p);
}

void build(int i, int l, int r) {
    if (l == r) return T[i].p = l, void();
    int m = l + r >> 1;
    build(lc, l, m); build(rc, m + 1, r);
    maintain(i, l, r);
}

void update(int i, int l, int r, int k) {
    if (l == r) return ; int m = l + r >> 1;
    if (k <= m) update(lc, l, m, k);
    else update(rc, m + 1, r, k);
    maintain(i, l, r);
}

int last;
int query(int i, int l, int r, int L, int R) {
    if (l > R || r < L) return 0;
    if (L <= l && r <= R) {
        pair<int, int> tmp = calc(i, l, r, last);
        last = tmp.second; return tmp.first;
    } int m = l + r >> 1; 
    return query(lc, l, m, L, R) + query(rc, m + 1, r, L, R); 
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n >> m; build(1, 1, n); 
    for (int i = 1; i <= m; ++i) {
        int x, y; cin >> x >> y;
        a[x] = 1.0 * y / x;
        update(1, 1, n, x);
        last = 1; cout << (a[1] > 0) + query(1, 1, n, 2, n) << "\n";
    } 
    return 0;
}