B3799题解
Light_az
·
·
题解
题意
给一个序列，现在有一下两种操作：
-
将整个序列的值加上 k。
-
求整个序列的正整数的和。
分析
对于数据范围，我们发现不能采用暴力解法，因此我们进行优化。
以下内容的变量名分别代表：
$num$：目前序列中有多少个正数（包括零）。
$cnt$：目前序列添加值的总和。
$k$：操作 $1$ 的添加值。
下面进行分类讨论：
当 $k$ 为正数时，因为正整数加正整数一定不变，所以序列正整数的总和一定会添加 $num \times k$。
当然有些负数会随着 $cnt$ 的增大最后变成正数，所以我们要从最大的负数向后枚举，如果 $a_{last} + cnt \ge 0 $，那么说明有负数变成正数，因此我们将 $num$ 增加，并且把答案加上 $a_{last} + cnt $ 的值，因为负数会抵消掉 $cnt$ 的一些值，所以我们不能直接添加，最后将 $last$ 后移。
当 $k$ 为负数时，首先我们要判断最小的正整数（即 $a_{last-1}$）是否会变成负数，如果 $a_{last-1} + cnt + k < 0$，那么说明有正数变成负数， 因此我们要减去这个正数的值，即 $a_{last-1} + cnt$ 的值，然后将 $num$ 的数量减少，$last$ 前移即可。
# 代码
```cpp
#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=1e6+10;
ll n,m,k,x,y,u,v,w,cnt,ans,t,l,r,len,T,id,sum,num,last=1;
ll mn=INT_MAX,mx=0,p,opt;
ll a[N];
bool cmp(ll a,ll b){
return a>b;
}
int main(){
cin>>n>>m;
F(i,1,n) cin>>a[i];
sort(a+1,a+1+n,cmp);//排序保证数据不上升
F(i,1,n){
last=i;//记录最大负数
if(a[i]<0) break;
num++;
sum+=a[i];
}
if(a[last]>=0) last++;//特判
F(i,1,m){
cin>>opt;
if(opt==1){
cin>>k;
while(last-1>=1&&a[last-1]+cnt+k<0) num--,sum-=a[last-1]+cnt,last--;
//注意优先级，因为 num*k 要保证全是正数，而由于 k 可能是负数导致 num 减少
//因此先判断负数的情况，减去答案贡献
//cnt不先加k 是因为 a[last-1]+cnt>0，而a[last-1]+cnt+k<0
//所以答案减去正数的贡献应该是 a[last-1]+cnt
cnt+=k;//累计添加操作
sum+=num*k;//懒惰操作
while(last<=n&&a[last]+cnt>=0) num++,sum+=a[last]+cnt,last++;
//有负数变成正数，下标后移
}
else cout<<sum<<"\n";
}
return 0;
}
```
# Hack
感谢 [MicroSun ](https://www.luogu.com.cn/user/514700) 指出，当整个数列都是正整数时，$last$ 指向了 $n$ 下标，我们只需要特判即可。