B3799题解

Light_az · 2023-06-23 23:09:14 · 题解

题意

现在给你一个长度为 n 的数列，支持以下操作：

• 将 n 个数全部加上 k。

• 求 n 个数中非负数的总和。

分析

观察数据范围发现桶可做，首先我们定义 ans 为添加操作 k 的总和，sum 为数列值的前缀和，cnt 为数量的前缀和，那么由于数据 -5 \times 10^5 \leq a_i \leq 5 \times 10^5，所以：

• 当 5 \times 10^5 \leq ans 时，数列中全部数都是非负数，累加和操作即可。

• 当 ans \leq -5 \times 10^5 时，数列中全部数都是负数，直接输出 0 即可。

• 当 -5 \times 10^5 \leq ans \leq 5 \times 10^5 时，此时原始状态的数列中，范围在 [-ans,5 \times 10^5] 中的数在加上 ans 都是非负数，预处理前缀和求出该区间总值以及数的个数并输出即可。

代码

#include<bits/stdc++.h>
#define ll long long
#define F(i,j,n) for(ll i=j;i<=n;i++)
#define D double
#define Test ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
using namespace std;
const int N=1e7+10;
ll n,m,k,x,y,u,v,w,ans,t,l,r,len,T,id;
ll mn=INT_MAX,mx=0,p,opt;
ll cnt[N],sum[N];
int main(){
    Test;
    cin>>n>>m;
    F(i,1,n){
        cin>>x;
        cnt[500000+x]++;//考虑有负数，加上 500000 防止越界
        sum[500000+x]+=x;
    }
    F(i,0,1000000) cnt[i]+=cnt[i-1],sum[i]+=sum[i-1];//处理数量以及总值的前缀和
    F(i,1,m){
        cin>>opt;
        if(opt==1) cin>>k,ans+=k;
        else{
            if(ans>500000) cout<<sum[1000000]+ans*cnt[1000000]<<"\n";//第一种情况
            else if(ans<-500000) cout<<0<<"\n";//第二种情况
            else cout<<sum[1000000]-sum[500000-ans]+ans*(cnt[1000000]-cnt[500000-ans])<<"\n";//最后一种
        }
    }
    return 0;
}