Luogu P3616 富金森林公园

题目描述

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

简要题意：给定一个长度为 $n$ 的序列 $a_i$，现在有 $m$ 次操作，操作分两种，第一种是给定一个整数 $h$，求如果将所有 $a_i$ 变成 $[a_i\ge h]$ 后有多少段连续的 $1$；第二种操作是给定 $x,y$，将 $a_x$ 变成 $y$

$n\le 2\times 10^5$

Solution

题目要求连通块，在这题中连通块的个数等于点的个数减掉边的个数

我们只需要维护出所有高度的点的个数和边的个数即可，离散化之后用树状数组实现即可

时间复杂度 $O(n\log n)$

#include <iostream>
#include <algorithm>
#define maxn 200010
#define maxm 200010
#define lowbit(i) ((i) & (-i)) 
using namespace std;

int n, m, a[maxn];

struct Query {
    int opt, x, y;
} Q[maxm];

int b[maxn * 2], cnt;
void init_hash() {
    for (int i = 1; i <= n; ++i) b[i] = a[i];
    for (int i = 1; i <= m; ++i)
        if (Q[i].opt == 1) b[i + n] = Q[i].x;
        else b[i + n] = Q[i].y;
    sort(b + 1, b + n + m + 1); cnt = unique(b + 1, b + n + m + 1) - b - 1;
    for (int i = 1; i <= n; ++i) a[i] = lower_bound(b, b + cnt + 1, a[i]) - b;
    for (int i = 1; i <= m; ++i)
        if (Q[i].opt == 1) Q[i].x = lower_bound(b + 1, b + cnt + 1, Q[i].x) - b;
        else Q[i].y = lower_bound(b + 1, b + cnt + 1, Q[i].y) - b; 
}

int Bit[maxn * 2][2];
void add(int i, int v, int o) { while (i <= cnt) Bit[i][o] += v, i += lowbit(i); }

void update(int l, int r, int v, int o) { add(l, v, o); add(r + 1, -v, o); }

int get_sum(int i, int o) {
    int s = 0;
    while (i) s += Bit[i][o], i -= lowbit(i);
    return s;
}

inline void update(int i, int v) {
    if (i > 1) update(1, min(a[i - 1], a[i]), -1, 0);
    if (i < n) update(1, min(a[i], a[i + 1]), -1, 0);
    add(a[i], -1, 1);
    a[i] = v; 
    if (i > 1) update(1, min(a[i - 1], a[i]), 1, 0);
    if (i < n) update(1, min(a[i], a[i + 1]), 1, 0);
    add(a[i], 1, 1); 
}

inline void solve_1(int x) {
    cout << n - get_sum(x - 1, 1) - get_sum(x, 0) << "\n"; 
}

inline void solve_2(int x, int y) {
    update(x, y); 
} 

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

    cin >> n >> m; 
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 1; i <= m; ++i) {
        cin >> Q[i].opt;
        if (Q[i].opt == 1) cin >> Q[i].x;
        else cin >> Q[i].x >> Q[i].y;
    } init_hash();
    for (int i = 1; i <= n; ++i) {
        add(a[i], 1, 1);
        if (i > 1) update(1, min(a[i - 1], a[i]), 1, 0);
    }
    for (int i = 1; i <= m; ++i)
        if (Q[i].opt == 1) solve_1(Q[i].x);
        else solve_2(Q[i].x, Q[i].y); 
    return 0;
}