写在前面
周末在家打牛客网，必出事
题目描述
小多有n个池塘，第i个池塘容量为i，一开始都没有水。
随后的很多天，第i天的天气状况决定了所有水池同时的水量变化bi，bi>0表示在下雨，反之则表示在干旱。
如果某个池塘满了，天还在下雨，那么多余的水就会白白流失掉。同样的，如果池塘干了还在干旱，池塘也不会出现负水量。更正式地说，设第k个水池当前水量为u，经历了某天，水量如果增加v，那么该水池在这天过后的水量为min(u+v,k)；若v是个负数（水量减少），那么水量为max(0,u+v)。
对于随后的q天，小多希望知道每一天结束时，所有池塘的总水量。
输入描述
第一行输入两个正整数n,q，表示小希的池塘数量和询问的天数。
第二行起q行，第i行表示第i天的天气情况导致水量的变化。
输出描述
输出q行，每一行输出一个整数totali，表示在第i天结束时，所有池塘的总水量。
示例1
输入
5 3
1
3
-2
输出
5
14
5
说明
第一天池塘水量分别为1,1,1,1,1。
第二天池塘水量分别为1,2,3,4,4。
第三天池塘水量分别为0,0,1,2,2。
备注:
对于100%的数据，n≤10, q≤10, −10≤bi≤10。
分析
牛客能看别人代码这点是真的爽
感性理解一下，水量一定是长成这个样子的
即水量一定是关于容量单增的，而且相邻容量之间最多差1，是一条斜率为1的斜线
而且，每过一天最多产生一条斜线，还有可能消除之前的直线。
所以，我们可以维护每一条斜线和整体的贡献。
最多$q$条斜线，每条斜线消除，加入各是$O(1)$的，所以复杂度算下来大概就是$O(q)$的，感觉海星
接下来考虑如何计算贡献
显然，最终的答案就是框起来部分的面积。
因为我们维护的是直线，为了方便计算，我们把它分割成这个亚子
每条斜线可以对应一个梯形或者是三角形的面积
所以只要维护每条斜线的右端点横坐标（绿线），左右端点高度差（红线）就可以计算每条斜线对应梯形的面积了
（因为底部的长度是知道的，就是n（蓝线））
于是我们可以用栈维护直线，每次水位变化时，找到哪些会被删除的直线，将它们暴力从栈弹出，顺便减去它们的贡献
然后再看是否会形成新的直线，然后计算新的贡献加到答案里去
Code
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=1000005;
int n,q,en;long long x,ans,h[maxn],w[maxn];
long long cal(long long h,long long w){return h*(h+1)/2+(n-w)*h;}
int main()
{
scanf("%d%d",&n,&q);
for(int i=1;i<=q;i++)
{
scanf("%lld",&x);
if(x>0)
{
while(en&&h[en]+x>=w[en])ans-=cal(h[en],w[en]),x+=h[en--];
h[++en]=min(x,1ll*n);w[en]=min(x,1ll*n);
ans+=cal(h[en],w[en]);
}
else
{
while(en&&h[en]+x<=0)ans-=cal(h[en],w[en]),x+=h[en--];
if(en)ans-=cal(h[en],w[en]),h[en]+=x,ans+=cal(h[en],w[en]);
}
printf("%lld\n",ans);
}
}