zcmimi's blog

查看原题

点击跳转

将草按生长速度排序,可以发现每次收割完草的高度仍为单调的

维护区间加,区间覆盖,区间和,区间最大值即可

#include<bits/stdc++.h>
typedef long long ll;
const int N=500011;
int n,m,a[N];ll b,S[N];
ll s[N<<2],mx[N<<2],laz[N<<2],cov[N<<2];
#define ls rt<<1
#define rs rt<<1|1
void upd(int x,ll d,int l,int r){
    s[x]+=(S[r]-S[l-1])*d,mx[x]+=a[r]*d,laz[x]+=d;
}
void set(int x,ll v,int l,int r){
    s[x]=(r-l+1)*v,mx[x]=v,cov[x]=v,laz[x]=0;
}
void pd(int rt,int l,int m,int r){
    if(~cov[rt])set(ls,cov[rt],l,m),set(rs,cov[rt],m+1,r),cov[rt]=-1;
    if(laz[rt])upd(ls,laz[rt],l,m),upd(rs,laz[rt],m+1,r),laz[rt]=0;
}
void cut(int l,int r,int rt){  
    if(l==r)return set(rt,b,l,r);
    int m=l+r>>1;pd(rt,l,m,r);
    if(mx[ls]>b)set(rs,b,m+1,r),cut(l,m,ls);
    else cut(m+1,r,rs);
    mx[rt]=mx[ls]>mx[rs]?mx[ls]:mx[rs];
    s[rt]=s[ls]+s[rs];
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)scanf("%d",a+i);
    std::sort(a+1,a+n+1);
    for(int i=1;i<=n;++i)S[i]=S[i-1]+a[i];
    memset(cov,-1,sizeof cov);
    ll ld=0,nd,t;
    for(int i=1;i<=m;++i){        
        scanf("%lld%lld",&nd,&b);
        upd(1,nd-ld,1,n);
        if(mx[1]<=b)puts("0");
        else t=s[1],cut(1,n,1),printf("%lld\n",t-s[1]);
        ld=nd;
    }
}
LG 5579 [PA2015]Siano
comment评论
Search
search