出题人题解 | #瑟班守护者莎利雅与护教军#

原题解链接：https://ac.nowcoder.com/discuss/150009

本题有多种做法。这里介绍一种奇特的做法。

首先离线,将所有出现值离散化。再用权值线段树维护当前兵力值序列中最左和最右的兵力值大于等于数$vv$的位置,分别记为$l_v,r_{v}l\_\{v\},\; r\_\{v\}$。考虑到兵力值序列一定是一个上凸的序列，所以整个序列中兵力值大于等于某个数的数的个数就是$r_v-l_v+1r\_\{v\}-l\_\{v\}+1$，回答询问时将左右端点限制在询问区间内即可。

查询整个序列的和只要对每一段$\mathrm{\Delta }v\backslash Delta\; v$求其出现次数，相乘就是这一段$\mathrm{\Delta }v\backslash Delta\; v$的贡献。全部求和就是答案。

可以发现修改操作只会修改线段树上一段区间。在线段树上二分修改到的区间的左右端点即可。

总复杂度$O(nlogn)O(nlogn)$。

#include <stdio.h>
int main()
{
    int n,m;
    int i,j;
    int x,l,r,v;
    int sign;
    int d[100000],f[100000];
    int count;
     
    int sum(int a[],int m,int n);
    int max(int a[],int m,int n);
    int max2(int a,int b);
    int min(int a,int b);
     
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++){
        scanf("%d",&d[i]);
    }
    for(j=1;j<=m;j++){
        scanf("%d",&sign);
        for(i=1;i<=n;i++){
            f[i]=max2(d[i],min(max(d,1,i-1),max(d,i+1,n)));
        }
        switch(sign){
            case 1: 
                printf("%d\n",sum(f,1,n));
                break;
            case 2:
                scanf("%d%d%d",&l,&r,&v);
                count=0;
                for(i=l;i<=r;i++){
                    if(f[i]>=v) count++;
                }
                printf("%d\n",count);
                break;
            case 3:
                scanf("%d%d",&x,&v);
                d[x]+=v;
                break;
            dault: break;
        }
    }
    return 0;
}
int sum(int a[],int m,int n)
{
    int i,sum=0;
    for(i=m;i<=n;i++){
        sum+=a[i];
    }
    return sum;
}
 
int max(int a[],int m,int n)
{
    int i,max;
    if(n<m) return 0;    
    else{
        max=a[m];
        for(i=m;i<=n;i++){
            if(max<a[i]) max=a[i];
        }
    return max;
    }
}
 
int max2(int a,int b)
{
    return a>b?a:b;
}
 
int min(int a,int b)
{
    return a<b?a:b;
}