有一些草，一开始高度都是0，它们的生长速率不同。
给你一些单增的日期，在这些日期要将>b的草的部分都割掉，问你每次割掉的部分有多少。
将草的生长速率从大到小排序，这样每次割掉的是一个后缀，而且不会影响它们生长速率的递增性。
就是三种操作，一种对一个后缀赋值，一种对整个数组作 + 另一个数组（d(i)-d(i-1)）*a，一种求区间和。
可以通过打标记的线段树实现，标记下放通过预处理生长速率数组的前缀和可以实现。
队友的代码：
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <map>
#include <cstring>
#include <vector>
#include <ctime>
using namespace std;
struct nod{
int l,r,ls,rs;
long long sum,ma,lazyd,lazyge;
}t[2000010];
int num[500010],n,m,i,p,now;
long long ans,pre,sum[500010],d,b;
char c;
void ge(int d,long long a)
{
t[d].lazyd=0;
t[d].lazyge=a;
t[d].sum=(t[d].r-t[d].l+1)*a;
t[d].ma=a;
}
void addday(int d,long long a)
{
t[d].lazyd+=a;
t[d].sum+=(sum[t[d].r]-sum[t[d].l-1])*a;
t[d].ma+=num[t[d].r]*a;
}
void lazy(int d)
{
int ls=t[d].ls,rs=t[d].rs;
if (t[d].lazyge!=-1)
{
ge(ls,t[d].lazyge);
ge(rs,t[d].lazyge);
t[d].lazyge=-1;
}
if (t[d].lazyd!=0)
{
addday(ls,t[d].lazyd);
addday(rs,t[d].lazyd);
t[d].lazyd=0;
}
}
int buildtree(int l,int r)
{
int k,mid;
k=++p;
t[k].l=l;
t[k].r=r;
t[k].lazyge=-1;
if (l==r) return k;
mid=(l+r)/2;
t[k].ls=buildtree(l,mid);
t[k].rs=buildtree(mid+1,r);
return k;
}
int find(int d,long long a)
{
if (t[d].l==t[d].r) return t[d].l;
lazy(d);
if (t[t[d].ls].ma>a) return find(t[d].ls,a);
return find(t[d].rs,a);
}
long long getsum(int d,int l,int r)
{
int mid;
if (l<=t[d].l && r>=t[d].r) return t[d].sum;
mid=(t[d].l+t[d].r)/2;
lazy(d);
if (r<=mid) return getsum(t[d].ls,l,r);
if (l>mid) return getsum(t[d].rs,l,r);
return getsum(t[d].ls,l,mid)+getsum(t[d].rs,mid+1,r);
}
void modify(int d,int l,int r,long long a)
{
int mid;
if (l<=t[d].l && r>=t[d].r)
{
ge(d,a);
return;
}
lazy(d);
mid=(t[d].l+t[d].r)/2;
if (l>mid) modify(t[d].rs,l,r,a);
if (r<=mid) modify(t[d].ls,l,r,a);
if (l<=mid && r>mid)
{
modify(t[d].ls,l,mid,a);
modify(t[d].rs,mid+1,r,a);
}
t[d].ma=max(t[t[d].ls].ma,t[t[d].rs].ma);
t[d].sum=(t[t[d].ls].sum+t[t[d].rs].sum);
}
long long read()
{
c=getchar(); ans=0;
while (c<'0' || c>'9') c=getchar();
while (c>='0' && c<='9')
{
ans=ans*10+c-48;
c=getchar();
}
return ans;
}
int main()
{
//freopen("ac.in","r",stdin);
//freopen("ac.out","w",stdout);
scanf("%d%d",&n,&m);
buildtree(1,n);
for (i=1;i<=n;i++) num[i]=read();
sort(num+1,num+n+1);
for (i=1;i<=n;i++) sum[i]=sum[i-1]+num[i];
for (i=1;i<=m;i++)
{
d=read(); b=read();
addday(1,d-pre);
if (t[1].ma<=b)
{
pre=d;
printf("0
");
continue;
}
now=find(1,b);
printf("%lld
",getsum(1,now,n)-b*(n-now+1));
modify(1,now,n,b);
pre=d;
}
}