P3616 富金森林公园题解

题意

给你 \(n\) 个点，有 \(m\) 次操作，每次操作可以改变一个数的值，也可以查询有多少连续的块，满足这个块内的所有数的值都大于查询的值。

分析

还是比较容易想到用数据结构或分块的，毕竟有同时存在修改和查询操作。但是维护什么？怎么维护？

既然我们无法直接维护答案，那我们去考虑答案有什么性质，能不能通过维护好几个东西给他乱搞出来。然后 ~~看完题解后~~ 就会了。

题解

分析一下性质。

先将相邻两个点间的边权赋值为这两个点的较小值，并设当前要查询的值（题里的海拔高度）为 \(x\)。通过手玩样例，我们发现，对于每一个块，块中点权小于 \(x\) 的点数 \(-\) 块中边权小于 \(x\) 的边数 \(= 1\)。那么我们就可以通过维护整个数列中的点权，以及整个数列中的边权来迅速求得块数。即，点权小于 \(x\) 的点数 \(-\) 块中边权小于 \(x\) 的边数 \(=\) 块数。那么就好说了，什么树状数组、线段树随便上就好了。

这里我选择的是常数小还好打的树状数组。

代码

//P3616 富金森林公园
#include <bits/stdc++.h>
#define M 200005

using namespace std;

inline int read() {
    int x = 0, s = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9') {
        if(ch == '-')
            s = -s;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9') {
        x = (x << 3) + (x << 1) + ch - '0';
        ch = getchar();
    }
    return x * s;
}

void write(int x) {
    if(x < 0)  {
        x = ~(x - 1);
        putchar('-');
    }
    if(x > 9)
        write(x / 10);
    putchar(x % 10 + 48);
}

int n, m, a[M], w[M << 1], len, tree1[M << 1], tree2[M << 1];

struct Q {
    int opt;
    int b;
    int c;
    int d;
}q[M];

inline int lowbit(int x) {return x & (-x);}

inline void add(int pos, int addend) {
    for(int i = pos; i <= len; i += lowbit(i))
        tree1[i] += addend;
}

inline void add_edge(int pos, int addend) {
    for(int i = pos; i <= len; i += lowbit(i))
        tree2[i] += addend;
}

inline int ask (int pos) {
    int ans = 0;
    for(int i = pos; i > 0; i -= lowbit(i))
        ans += tree1[i];
    return ans;
}

inline int ask_edge (int pos) {
    int ans = 0;
    for(int i = pos; i > 0; i -= lowbit(i))
        ans += tree2[i];
    return ans;
}

signed main() {
    n = read();
    m = read();
    len = n + m;
    for(int i = 1; i <= n; ++ i)
        w[i] = a[i] = read();
    for(int i = 1; i <= m; ++ i) {
        q[i].opt = read();
        if(q[i].opt == 1) {
            q[i].b = read();
            w[n + i] = q[i].b;
        }
        else {
            q[i].c = read();
            q[i].d = read();
            w[n + i] = q[i].d;
        }
    }
    stable_sort(w + 1, w + len + 1);
    int l = unique(w + 1, w + 1 + len) - w - 1;
    for(int i = 1; i <= n ; ++ i )  {
        a[i] = lower_bound(w + 1, w + 1 + l, a[i]) - w;
        add(a[i], 1);
        if(i > 1)
            add_edge(min(a[i], a[i - 1]), 1);
    }
    for(int i = 1; i <= m; ++ i) {
        if(q[i].opt == 1) {
            q[i].b = lower_bound (w + 1, w + 1 + l, q[i].b) - w;
            write(ask_edge(q[i].b - 1) - ask(q[i].b - 1) + 1);
            putchar('\n');
        }
        else {
            int pos = q[i].c;
            q[i].d = lower_bound(w + 1, w + 1 + l, q[i].d) - w;
            add(q[i].d, 1);
            add(a[pos], -1);
            if(pos != 1) {
                add_edge(min(q[i].d, a[pos - 1]), 1);
                add_edge(min(a[pos], a[pos - 1]), -1);
            }
            if(pos != n) {
                add_edge(min(q[i].d, a[pos + 1]), 1);
                add_edge(min(a[pos], a[pos + 1]), -1);
            }
            a[pos] = q[i].d;
        }
    }
}