洛谷 3616 富金森林公园

考察一点思维能力的数据结构水题……

如果 wi=[ai≥b]，其中 ai 表示第 i 块巨石的海拔，b 表示当前海拔，容易发现答案就是 n∑i=1wi−n∑i=2min(wi,wi−1)。
为什么呢？每一个连续段的开头的前一个必定是 0（除了 a1 作为开头的），故第二个和式统计所有非开头的 1 的个数。
每一个开头就能对应一个连续段，于是答案就出来了。

随便用个数据结构维护就行了，平衡树树状数组线段树随便写。

代码：

#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 2e5;
const int C = 1e9;
int n,m,a[N + 5];
struct node
{
    int sum;
    int ls,rs;
} seg[(N << 6) + 10];
int rt1,rt2;
void insert(int x,int k,int &p,int tl,int tr)
{
    static int tot = 0;
    !p && (p = ++tot),seg[p].sum += k;
    if(tl == tr)
        return ;
    int mid = tl + tr >> 1;
    x <= mid ? insert(x,k,seg[p].ls,tl,mid) : insert(x,k,seg[p].rs,mid + 1,tr);
}
int query(int l,int r,int p,int tl,int tr)
{
    if(!p || (l <= tl && tr <= r))
        return seg[p].sum;
    int ret = 0;
    int mid = tl + tr >> 1;
    l <= mid && (ret += query(l,r,seg[p].ls,tl,mid));
    r > mid && (ret += query(l,r,seg[p].rs,mid + 1,tr));
    return ret;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(register int i = 1;i <= n;++i)
        scanf("%d",a + i),insert(a[i],1,rt1,1,C),i > 1 && (insert(min(a[i],a[i - 1]),1,rt2,1,C),1);
    int op,x,k;
    for(;m;--m)
    {
        scanf("%d%d",&op,&x);
        if(op == 1)
            printf("%d\n",query(x,C,rt1,1,C) - query(x,C,rt2,1,C));
        else
        {
            scanf("%d",&k);
            insert(a[x],-1,rt1,1,C),x > 1 && (insert(min(a[x],a[x - 1]),-1,rt2,1,C),1),x < n && (insert(min(a[x],a[x + 1]),-1,rt2,1,C),1);
            a[x] = k;
            insert(a[x],1,rt1,1,C),x > 1 && (insert(min(a[x],a[x - 1]),1,rt2,1,C),1),x < n && (insert(min(a[x],a[x + 1]),1,rt2,1,C),1);
        }
    }
}