Luogu 3616 富金森林公园

刚看到此题的时候：sb分块？？?
Rorshach dalao甩手一句看题
于是回去看题……果然是题读错了……

[思路]
对权值离散化后（要先读入所有输入里的权值一起离散化……所以一共有4e4个数据（~~当然你也可以不读入 hehe~~~~）） 建立一颗线段树， 线段树单点维护每一个海拔下的答案
好了问题来了， 怎么算答案呢？
我们从前到后开始扫描， 假设当前扫描到i， 离散化后的权值是now， 设它前一个离散化后的权值是pre， 那么假如（pre < now） 这一个点对答案的贡献值就是[pre + 1, now] 这个区间加一， 当然if不成立的话是不会产生贡献的
好了画样例理解一下， 我认为正确性比较显然

那么如何处理修改的操作呢？
只要先判断一下是否产生贡献， 如果有贡献就通过区间-1消去， 然后再进行重新更新即可   

Code：

#include <cstdio>
#include <algorithm>
using namespace std;

const int N = 4e5 + 5;
const int inf = 1 << 30;

int n, m, tot = 0, maxn =0, a[N], in[N];

struct Query {
    int op, pos, val;
} qn[N];

struct SegmentTree {
    int s[N << 2], tag[N << 2];
    
    #define lc p << 1
    #define rc p << 1 | 1
    #define mid (l + r) / 2

    inline void up(int p) {
        s[p] = s[lc] + s[rc];
    }

    inline void down(int p, int l, int r) {
        if(!tag[p]) return;
        s[lc] += (mid - l + 1) * tag[p];
        s[rc] += (r - mid) * tag[p];
        tag[lc] += tag[p], tag[rc] += tag[p];
        tag[p] = 0;
    }

    void modify(int p, int l, int r, int x, int y, int v) {
        if(x <= l && y >= r) {
            s[p] += (r - l + 1) * v;
            tag[p] += v;
            return;
        }

        down(p, l, r);
        if(x <= mid) modify(lc, l, mid, x, y, v);
        if(y > mid) modify(rc, mid + 1, r, x, y, v);
        up(p);
    }

    int query(int p, int l, int r, int x) {
        if(l == x && x == r) return s[p];
        down(p, l, r);
        int res = 0;
        if(x <= mid) res = query(lc, l, mid, x);
        else res = query(rc, mid + 1, r, x);
        return res;
    }

} seg;

inline void read(int &X) {
    X = 0;
    char ch = 0;
    int op = 1;
    for(; ch > '9' || ch < '0'; ch = getchar())
        if(ch == '-') op = -1;
    for(; ch >= '0' && ch <= '9'; ch = getchar())
        X = (X << 3) + (X << 1) + ch - 48;
    X *= op;
}

inline void discrete() {
    in[0] = -inf;
    sort(in + 1, in + 1 + tot);
    for(int i = 1; i <= tot; i++) {
        if(in[i] != in[i - 1]) maxn++;
        in[maxn] = in[i];
    }
}

inline int getVal(int v) {
    int ln = 1, rn = maxn, midn;
    for(; ln <= rn; ) {
        midn = (ln + rn) / 2;
        if(in[midn] == v) return midn;
        if(in[midn] < v) ln = midn + 1;
        else rn = midn - 1;
    }
    return -1;
}

inline void init() {
    int now, pre = 0;
    for(int i = 1; i <= n; i++, pre = now) {
        now = getVal(a[i]);
        if(now > pre) seg.modify(1, 1, maxn, pre + 1, now, 1);
    }
}

inline void solve() {
    for(int i = 1; i <= m; i++) {
        int v = getVal(qn[i].val);
        if(qn[i].op == 1) {
            if(qn[i].val == 0) puts("1");
            else printf("%d\n", seg.query(1, 1, maxn, v));
        } else {
            int pre = getVal(a[qn[i].pos - 1]), now = getVal(a[qn[i].pos]), nxt = getVal(a[qn[i].pos + 1]);
            if(pre < now) seg.modify(1, 1, maxn, pre + 1, now, -1);
            if(now < nxt) seg.modify(1, 1, maxn, now + 1, nxt, -1);
            now = getVal(a[qn[i].pos] = qn[i].val);
            if(pre < now) seg.modify(1, 1, maxn, pre + 1, now, 1);
            if(now < nxt) seg.modify(1, 1, maxn, now + 1, nxt, 1);
        }
    }
}

int main() {
    read(n), read(m);
    for(int i = 1; i <= n; i++) {
        read(a[i]);
        in[++tot] = a[i];
    }
    for(int i = 1; i <= m; i++) {
        read(qn[i].op);
        if(qn[i].op == 1) {
            read(qn[i].val);
            in[++tot] = qn[i].val;
        } else {
            read(qn[i].pos), read(qn[i].val);
            in[++tot] = qn[i].val;
        }
    }
    
    discrete();
    init();
    solve();

    return 0;
}