zcmimi's blog
avatar
zc
2020-07-25 23:00:00
  • 本文总阅读量
查看原题

点击跳转

题意:

  1. 区间加
  2. 求序列最大前缀和

区间加,相当于前缀和加上一个等差数列

而等差数列加上一个等差数列还是等差数列

考虑将每个位置的前缀和转化为一个一次函数kx+b

分块,对每个块维护一个上凸壳单调栈,可以二分找到最大值

#include<bits/stdc++.h>
const int N=100011;
int n,q,blk,bl[N],L[320],R[320],st[320][320],cnt[320];
typedef long long ll;
const ll inf=-1ull>>1;
ll a[N],k[320],add[320];
void cmax(ll&x,ll y){if(x<y)x=y;}
bool cmp(int x,int y,int X,int Y){return (a[x]-a[y])*(X-Y)<(a[X]-a[Y])*(x-y);}
void build(int x){
    int*sta=st[x];int&tp=cnt[x];
    sta[tp=1]=L[x];
    for(int i=L[x]+1;i<=R[x];++i){
        while(tp>1&&cmp(sta[tp-1],sta[tp],sta[tp-1],i))--tp;
        sta[++tp]=i;
    }
    sta[0]=0,sta[++tp]=n+1;
}
void pd(int x){
    ll s=0;
    for(int i=L[x];i<=R[x];++i)
        a[i]+=s,s+=k[x],a[i]+=add[x];
    k[x]=add[x]=0;
}
void upd(int l,int r,ll v){
    ll s=0;
    if(bl[l]==bl[r]){
        pd(bl[l]);
        for(int i=l;i<=r;++i)a[i]+=s+=v;

        s=v*(r-l+1);
        for(int i=r+1;i<=R[bl[r]];++i)a[i]+=s;
        build(bl[l]);
        for(int i=bl[l]+1;i<=bl[n];++i)add[i]+=s;
        return;
    }
    s=v*(L[bl[l]+1]-l+1);
    for(int i=bl[l]+1;i<bl[r];++i)
        add[i]+=s,k[i]+=v,s+=blk*v;

    pd(bl[l]);
    s=0;for(int i=l;i<=R[bl[l]];++i)a[i]+=s+=v;
    build(bl[l]);

    pd(bl[r]);
    s=v*(L[bl[r]]-l+1);
    for(int i=L[bl[r]];i<=r;++i)a[i]+=s,s+=v;

    s=v*(r-l+1);
    for(int i=r+1;i<=R[bl[r]];++i)a[i]+=s;

    build(bl[r]);
    for(int i=bl[r]+1;i<=bl[n];++i)add[i]+=s;
}
ll get(int x){return a[x]+k[bl[x]]*(x-L[bl[x]])+add[bl[x]];}
ll qry(int x){
    int l=1,r=cnt[x],m;
    int*sta=st[x];
    while(l<=r){
        m=l+r>>1;
        ll t1=get(sta[m-1]),t2=get(sta[m]),t3=get(sta[m+1]);
        if(t1<t2&&t2<t3)l=m+1;
        else{
            if(t1>t2&&t2>t3)r=m-1;
            else return t2;
        }
    }
}
ll ask(int l,int r){
    ll res=-inf;
    if(bl[l]==bl[r]){
        for(int i=l;i<=r;++i)cmax(res,get(i));
        return res;
    }
    for(int i=l;i<=R[bl[l]];++i)cmax(res,get(i));
    for(int i=bl[l]+1;i<bl[r];++i)cmax(res,qry(i));
    for(int i=r;i>=L[bl[r]];--i)cmax(res,get(i));
    return res;
}
int main(){
    scanf("%d",&n);blk=sqrt(n);
    for(int i=1;i<=n;++i)
        scanf("%lld",a+i),a[i]+=a[i-1],
        bl[i]=(i-1)/blk+1;
    a[0]=a[n+1]=-inf;
    for(int i=1;i<=bl[n];++i)
        L[i]=R[i-1]+1,R[i]=R[i-1]+blk;
    R[bl[n]]=n;
    for(int i=1;i<=bl[n];++i)build(i);
    scanf("%d",&q);
    while(q--){
        int opt,x,y;ll k;
        scanf("%d%d%d",&opt,&x,&y);
        if(opt==1)printf("%lld\n",ask(x,y));
        else scanf("%lld",&k),upd(x,y,k);
    }
}
LG 4192 旅行规划
comment评论
Search
search