线段树模板题，需要满足区间add和区间set，维护区间和及区间最大值。 有一个非常鬼畜的pushdown，注意必须先处理set标记，再处理add标记，set后要清空add标记。
#include#include #include using namespace std;typedef long long ll;const int N=500005;int n,m,w;ll d,b,ld,tmp,a[N],s[N],addv[N*4],setv[N*4],maxv[N*4],sumv[N*4];void pushdown(int o,int l,int r){ int mid=(l+r)/2; if(~setv[o]){ addv[o*2]=0; addv[o*2+1]=0; setv[o*2]=setv[o]; setv[o*2+1]=setv[o]; maxv[o*2]=setv[o]; maxv[o*2+1]=setv[o]; sumv[o*2]=setv[o]*(mid-l+1); sumv[o*2+1]=setv[o]*(r-mid); setv[o]=-1; } if(addv[o]){ addv[o*2]+=addv[o]; addv[o*2+1]+=addv[o]; maxv[o*2]+=addv[o]*a[mid]; maxv[o*2+1]+=addv[o]*a[r]; sumv[o*2]+=addv[o]*(s[mid]-s[l-1]); sumv[o*2+1]+=addv[o]*(s[r]-s[mid]); addv[o]=0; }}void get(int o,int l,int r,ll v){ if(l==r){ w=l; return; } pushdown(o,l,r); int mid=(l+r)/2; if(maxv[o*2]>=v){ get(o*2,l,mid,v); }else if(maxv[o*2+1]>=v){ get(o*2+1,mid+1,r,v); }else{ w=0; }}ll query(int o,int l,int r,int L,int R){ if(L<=l&&R>=r){ return sumv[o]; } pushdown(o,l,r); int mid=(l+r)/2; ll res=0; if(L<=mid){ res+=query(o*2,l,mid,L,R); } if(R>mid){ res+=query(o*2+1,mid+1,r,L,R); } return res;}void set(int o,int l,int r,int L,int R,ll v){ if(L<=l&&R>=r){ addv[o]=0; setv[o]=v; maxv[o]=v; sumv[o]=v*(r-l+1); return; } pushdown(o,l,r); int mid=(l+r)/2; if(L<=mid){ set(o*2,l,mid,L,R,v); } if(R>mid){ set(o*2+1,mid+1,r,L,R,v); } maxv[o]=max(maxv[o*2],maxv[o*2+1]); sumv[o]=sumv[o*2]+sumv[o*2+1];}int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++){ scanf("%lld",&a[i]); } sort(a+1,a+n+1); for(int i=1;i<=n;i++){ s[i]=s[i-1]+a[i]; } memset(setv,-1,sizeof(setv)); for(int i=1;i<=m;i++){ scanf("%lld%lld",&d,&b); tmp=d-ld; addv[1]+=tmp; maxv[1]+=tmp*a[n]; sumv[1]+=tmp*s[n]; if(b>maxv[1]){ puts("0"); ld=d; continue; } get(1,1,n,b); printf("%lld\n",query(1,1,n,w,n)-b*(n-w+1)); set(1,1,n,w,n,b); ld=d; } return 0;}