求助 #21

卡了很久还是过不了。

#include<bits/stdc++.h>
using namespace std;
long long TMP=0;

namespace fastio
{
    const int bufl=1<<20;
    const double base1[16]={1,1e-1,1e-2,1e-3,1e-4,1e-5,1e-6,1e-7,1e-8,1e-9,1e-10,1e-11,1e-12,1e-13,1e-14,1e-15};
    const double base2[16]={1,1e1,1e2,1e3,1e4,1e5,1e6,1e7,1e8,1e9,1e10,1e11,1e12,1e13,1e14,1e15};
    struct IN{
        FILE *IT;char ibuf[bufl],*is=ibuf,*it=ibuf;
        IN(){IT=stdin;}IN(char *a){IT=fopen(a,"r");}
        inline char getChar(){if(is==it){it=(is=ibuf)+fread(ibuf,1,bufl,IT);if(is==it)return EOF;}return *is++;}
        template<typename Temp>inline void getInt(Temp &a){a=0;int b=0,c=getChar();while(c<48||c>57)b^=(c==45),c=getChar();while(c>=48&&c<=57)a=(a<<1)+(a<<3)+c-48,c=getChar();if(b)a=-a;}
        IN& operator>>(int &a){getInt(a);return *this;}
        IN& operator>>(long long &a){getInt(a);return *this;}
    };
    struct OUT{
        FILE *IT;char obuf[bufl],*os=obuf,*ot=obuf+bufl;int Eps;long double Acc;
        OUT(){IT=stdout,Eps=6,Acc=1e-6;}OUT(char *a){IT=fopen(a,"w"),Eps=6,Acc=1e-6;}
        inline void ChangEps(int x=6){Eps=x;}
        inline void flush(){fwrite(obuf,1,os-obuf,IT);os=obuf;}
        inline void putChar(int a){*os++=a;if(os==ot)flush();}
        template<typename Temp>inline void putInt(Temp a){if(a<0){putChar(45);a=-a;}if(a<10){putChar(a+48);return;}putInt(a/10);putChar(a%10+48);}
        template<typename Temp>inline void putLeading(Temp a,int b){if(!b)return;putLeading(a/10,b-1);putChar(a%10+48);}
        template<typename Temp>inline void putDouble(Temp a){if(a<0){putChar(45);a=-a;}__int128 b=a;putInt(b);a-=b;a*=base2[Eps];b=a+Acc;putChar(46);putLeading(b,Eps);}
        OUT& operator<<(char a){putChar(a);return *this;}
        OUT& operator<<(char *a){while(*a>32)putChar(*a++);return *this;}
        OUT& operator<<(int a){putInt(a);return *this;}
        OUT& operator<<(long long a){putInt(a);return *this;}
        ~OUT(){flush();}
    };
}
using fastio::IN;
using fastio::OUT;
IN fin;
OUT fout;
#define cin fin
#define cout fout
const int J=2005;
const int N=1e5,S=600;
const long long inf=0x3f3f3f3f3f3f3f3fll;
int bl[N/S+5],br[N/S+5],qcnt,pos[100005],n,m,a[100005];
struct Point{
    long long x,y;
    inline Point operator + (const Point& b)const{return {x+b.x,y+b.y};}
    inline Point operator - (const Point& b)const{return {x-b.x,y-b.y};}
    inline long long operator *(const Point& b)const{return x*b.y-y*b.x;}
    inline bool operator <= (const Point& x)const{return (*this)*x<=0;}
};
Point pool[100005];
int ptop;
struct Hull{
    int mxpnt,siz;
    long long tag;
//  vector<Point>Po;
    Point * Po;
    inline Point operator [](const int& x)const{return {Po[x].x,Po[x].y+tag*Po[x].x};}
    inline void Push_back(Point x){Po[siz++]=x;return;}
    inline void Insert(Point x){Po[x.x].y=max(Po[x.x].y,x.y);}
    inline void Empty(int len){
        Po[0]={0,0};
        tag=0;
        mxpnt=0;
        siz=len+1;
        for(int i=1;i<=len;i++)Po[i]={i,-inf};

    }
    inline void Convex(){
        if(siz<=2)return;
        tag=0;
        int nsiz=1;
        for(int i=2;i<siz;i++){
            if(Po[i].y==-inf)continue;
            while(nsiz>=1&&Po[i]-Po[nsiz-1]<=Po[nsiz]-Po[nsiz-1]){
//              cout<<"POP "<<Po[nsiz].x<<" "<<Po[nsiz].y<<"\n";
                nsiz--;
            }
            Po[++nsiz]=Po[i];
        }
        siz=nsiz+1;
    }
    /*
    0 0
    1 -2
    1 -2
    2 -1
    */
    inline long long Maxn(long long addv){
        while(mxpnt<siz-1&&Po[mxpnt].x*(tag+addv)+Po[mxpnt].y<Po[mxpnt+1].x*(tag+addv)+Po[mxpnt+1].y)mxpnt++;
        return Po[mxpnt].x*(tag+addv)+Po[mxpnt].y;
    }
    inline long long Maxn_Binary(long long addv){
        int l=-1,r=siz-1;
        while(l<r-1){
            int mid=(l+r)>>1;
            if((Po[mid+1].x-Po[mid].x)*(tag+addv)+Po[mid+1].y-Po[mid].y>0)l=mid;
            else r=mid;
        }
        mxpnt=r;
        return Po[r].x*(tag+addv)+Po[r].y;
    } 
};
struct Result{
    long long lmax,rmax,sum,ansmax;
    inline Result operator +(const Result& x){return {max(lmax,sum+x.lmax),max(rmax+x.sum,x.rmax),sum+x.sum,max(x.ansmax,max(x.lmax+rmax,ansmax))};}
};
Result ans[100005];
struct Infor{
    int l,r;
    long long sum,tag;
    Hull rmax,lmax,ansmax;
};
struct Segment_Tree{
    Infor sg[(S<<2)+5];
    inline void Mukiowski(Hull& c,Hull& a,Hull& b){
        int i=0,j=0,siza=a.siz,sizb=b.siz;
        c.Insert(a[i]+b[j]);
        while(i<siza-1&&j<sizb-1){
            if(a[i+1]-a[i]<=b[j+1]-b[j])i++;
            else j++;
            c.Insert(a[i]+b[j]);
        }
        while(i<siza-1){
            i++;
            c.Insert(a[i]+b[j]);
        }
        while(j<sizb-1){
            j++;
            c.Insert(a[i]+b[j]);
        }
    }
    inline void PreMerge(Hull& c,Hull& a,Hull& b,Point addv){
        int siza=a.siz,sizb=b.siz;
//      cout<<siza<<"\n";
        for(int i=0;i<siza;i++){
            c.Push_back(a[i]);
//          cout<<a[i].x<<" "<<a[i].y<<"\n";
        }
        for(int i=0;i<sizb;i++){
            c.Push_back(b[i]+addv);
//          cout<<(b[i]+addv).x<<" "<<(b[i]+addv).y<<"\n";
        }
//      cout<<"c:"<<"\n";
//      for(int i=0;i<c.siz;i++)cout<<c[i].x<<" "<<c[i].y<<"\n";
        c.Convex();
//      cout<<"c:"<<"\n";
//      for(int i=0;i<c.siz;i++)cout<<c[i].x<<" "<<c[i].y<<"\n";
    }
    inline void Allocate(int rt,int l,int r){
        sg[rt].lmax.Po=pool+ptop;
        ptop+=r-l+3;
        sg[rt].rmax.Po=pool+ptop;
        ptop+=r-l+3;
        sg[rt].ansmax.Po=pool+ptop;
        ptop+=r-l+3;
        if(l==r)return;
        int mid=(l+r)>>1;
        Allocate(rt<<1,l,mid);
        Allocate(rt<<1|1,mid+1,r);
    }
    inline void Push_up(int rt){
        int mid=(sg[rt].l+sg[rt].r)>>1;
//      for(int i=0;i<sg[rt<<1|1].lmax.siz;i++)cout<<(sg[rt<<1|1].lmax[i]+(Point){mid-sg[rt].l+1,sg[rt<<1].sum}).y<<" ";
//      cout<<"\n";
        PreMerge(sg[rt].lmax,sg[rt<<1].lmax,sg[rt<<1|1].lmax,{mid-sg[rt].l+1,sg[rt<<1].sum});
        PreMerge(sg[rt].rmax,sg[rt<<1|1].rmax,sg[rt<<1].rmax,{sg[rt].r-mid,sg[rt<<1|1].sum});
        sg[rt].ansmax.Empty(sg[rt].r-sg[rt].l+1);
        for(int i=0;i<sg[rt<<1].ansmax.siz;i++)sg[rt].ansmax.Insert(sg[rt<<1].ansmax[i]);
        for(int i=0;i<sg[rt<<1|1].ansmax.siz;i++)sg[rt].ansmax.Insert(sg[rt<<1|1].ansmax[i]);
        Mukiowski(sg[rt].ansmax,sg[rt<<1].rmax,sg[rt<<1|1].lmax);
        sg[rt].ansmax.Convex();
        sg[rt].lmax.mxpnt=sg[rt].rmax.mxpnt=sg[rt].ansmax.mxpnt=0;
        sg[rt].lmax.tag=sg[rt].rmax.tag=sg[rt].ansmax.tag=0;
        sg[rt].sum=sg[rt<<1].sum+sg[rt<<1|1].sum;
        return;
    }
    inline void Build(int rt,int L,int R){
        sg[rt].l=L,sg[rt].r=R,sg[rt].tag=0,sg[rt].sum=0;
        sg[rt].lmax.siz=0;
        sg[rt].rmax.siz=0;
        sg[rt].ansmax.siz=0;
        sg[rt].lmax.tag=0;
        sg[rt].rmax.tag=0;
        sg[rt].ansmax.tag=0;
        sg[rt].lmax.mxpnt=0;
        sg[rt].rmax.mxpnt=0;
        sg[rt].ansmax.mxpnt=0;
        if(L==R){
            sg[rt].sum=a[L+TMP];
            sg[rt].rmax.Push_back({0,0});
            sg[rt].lmax.Push_back({0,0});
            sg[rt].ansmax.Push_back({0,0});
            sg[rt].rmax.Push_back({1,a[L+TMP]});
            sg[rt].lmax.Push_back({1,a[L+TMP]});
            sg[rt].ansmax.Push_back({1,a[L+TMP]});
            return;
        } 
        int mid=(L+R)>>1;
        Build(rt<<1,L,mid),Build(rt<<1|1,mid+1,R);
        Push_up(rt);
    }
    inline void Push_down(int rt){
        long long T=sg[rt].tag;
        if(T==0)return;
        sg[rt].tag=0;
        sg[rt<<1].lmax.tag+=T;
        sg[rt<<1].rmax.tag+=T;
        sg[rt<<1].ansmax.tag+=T;
        sg[rt<<1|1].lmax.tag+=T;
        sg[rt<<1|1].rmax.tag+=T;
        sg[rt<<1|1].ansmax.tag+=T;
        sg[rt<<1].sum+=T*(sg[rt<<1].r-sg[rt<<1].l+1);
        sg[rt<<1|1].sum+=T*(sg[rt<<1|1].r-sg[rt<<1|1].l+1);
        sg[rt<<1].tag+=T;
        sg[rt<<1|1].tag+=T;

    }
    inline void Add(int rt,int L,int R,long long k){
        if(L<=sg[rt].l&&sg[rt].r<=R){

            sg[rt].lmax.tag+=k;
            sg[rt].rmax.tag+=k;
            sg[rt].ansmax.tag+=k;
            sg[rt].sum+=k*(sg[rt].r-sg[rt].l+1);
            sg[rt].tag+=k;
//          cout<<"SGT:"<<rt<<"\n";
//          for(int i=0;i<sg[rt].rmax.siz;i++)cout<<sg[rt].rmax[i].y<<" ";
//          cout<<"\n";
            return ;
        }
        Push_down(rt);
        int mid=(sg[rt].l+sg[rt].r)>>1;
        if(L<=mid)Add(rt<<1,L,R,k);
        if(R>=mid+1)Add(rt<<1|1,L,R,k);
        sg[rt].lmax.siz=0;sg[rt].rmax.siz=0;sg[rt].ansmax.siz=0;
//      cout<<"Merge: "<<rt<<"\n";
        Push_up(rt);
//      cout<<"SGT:"<<rt<<"\n";
//      for(int i=0;i<sg[rt].lmax.siz;i++)cout<<sg[rt].lmax[i].y<<" ";
//      cout<<"\n";
        return;
    }
    inline Result Allquery(long long addv){
        return {sg[1].lmax.Maxn(addv),sg[1].rmax.Maxn(addv),sg[1].sum+(sg[1].r-sg[1].l+1)*addv,sg[1].ansmax.Maxn(addv)};
    }
    inline Result Query(int rt,int L,int R,long long addv){
        if(rt==1&& L==sg[1].l&&R==sg[1].r)return Allquery(addv);
        if(L<=sg[rt].l&&sg[rt].r<=R)return {sg[rt].lmax.Maxn_Binary(addv),sg[rt].rmax.Maxn_Binary(addv),sg[rt].sum+(sg[rt].r-sg[rt].l+1)*addv,sg[rt].ansmax.Maxn_Binary(addv)};
        Result S={0,0,0,0};
        Push_down(rt);
        int mid=(sg[rt].l+sg[rt].r)>>1;
        if(L<=mid)S=S+Query(rt<<1,L,R,addv);
        if(R>=mid+1)S=S+Query(rt<<1|1,L,R,addv);
        return S; 
    } 
//  inline void Clear(int rt){
//      sg[rt].tag=0;
//      sg[rt].sum=0;
//      
//      if(sg[rt].l==sg[rt].r)return;
//      Clear(rt<<1),Clear(rt<<1|1);
//  }
};
struct Opt{
    int type,l,r,id;
    long long v;
    bool operator <(const Opt& x){return v<x.v;}
};
int CNT=0;
const int JS=255;
struct Block{
    Segment_Tree sgt;
    int n,m,bid,cnt[S+1];
    Opt seq[100005],tmp[100005];
    long long mrk,val[100005],valt[100005];
    inline void AllAdd(long long addv){mrk+=addv;}
    inline void PartAdd(int l,int r,long long addv){
        if(addv==0)return;
        if(l==1&&r==n){
            mrk+=addv;
            return;
        }
        seq[++m]={addv,l,r,0,mrk};
    }
    inline void Query(int l,int r,int idx){seq[++m]={0,l,r,idx,mrk};}
    inline void Sort(int l,int r){
        if(r-l<=512){
            sort(seq+l,seq+r+1);
            return;
        }
        for(int i=l;i<=r;i++)val[i-l]=valt[i-l]=seq[i].v|((1ll*i)<<35);
        for(int i=0;i<32;i+=8){
            memset(cnt,0,sizeof(cnt));
            for(int j=0;j<=r-l;j++)cnt[(val[j]>>i)&JS]++;
            for(int j=1;j<=JS;j++)cnt[j]+=cnt[j-1];
            for(int j=r-l;j>=0;j--){
                valt[cnt[(val[j]>>i)&JS]-1]=val[j];
                cnt[(val[j]>>i)&JS]--;
            }
            memcpy(val,valt,(r-l+5)*(sizeof(long long)));
//          for(int j=0;j<=r-l;j++)val[j]=valt[j];
        }
        for(int i=l;i<=r;i++)tmp[i]=seq[i];
        for(int i=l;i<=r;i++)seq[i]=tmp[(val[i-l]>>35)];
    }
    inline void Prefix(){
//      cout<<"Bid:"<< bid<<"\n";
        long long minmrk=0;
        for(int i=1;i<=m;i++)minmrk=min(minmrk,seq[i].v);
        for(int i=1;i<=m;i++)seq[i].v-=minmrk;
        for(int i=bl[bid];i<=br[bid];i++)a[i]+=minmrk;
        TMP=(bid-1)*S;
        sgt.Build(1,1,n);
        int last=1;
        for(int i=1;i<=m;i++){
            if(seq[i].type!=0){
                if(i!=last)Sort(last,i-1);
                last=i+1;
            }
        }
        if(last<m)Sort(last,m);
    }
    inline void Solve(){
//      cout<<m<<"\n";
        for(int i=1;i<=m;i++){
//          cout<<"Solve:"<<seq[i].l<<" "<<seq[i].r<<"\n";
            if(seq[i].type==0){
                if((i^1)&&seq[i-1].type){
//                  sgt.sg[1].ansmax.mxpnt=sgt.sg[1].ansmax.siz-1;
//                  sgt.sg[1].rmax.mxpnt=sgt.sg[1].rmax.siz-1;
//                  sgt.sg[1].lmax.mxpnt=sgt.sg[1].lmax.siz-1;
                    sgt.sg[1].lmax.Maxn_Binary(seq[i].v);
                    sgt.sg[1].rmax.Maxn_Binary(seq[i].v);
                    sgt.sg[1].rmax.Maxn_Binary(seq[i].v); 
//                  CNT++;
                }
                Result tmp=sgt.Query(1,seq[i].l,seq[i].r,seq[i].v);
//              cout<<tmp.lmax<<" "<<tmp.rmax<<' '<<tmp.sum<<" "<<tmp.ansmax<<"\n";
                ans[seq[i].id]=ans[seq[i].id]+tmp;
            }else sgt.Add(1,seq[i].l,seq[i].r,seq[i].type);
        }
    }
    inline void Clear(){
        m=0;
//      sgt.Clear(1);
        mrk=0;
    }
}blk;
struct Op{
    int opt,l,r;
    long long v;
};
Op rp[100005];
int main(){
//  ios::sync_with_stdio(0);
//  cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        pos[i]=(i-1)/S+1;
    }
    for(int i=1;i<=m;i++){
        cin>>rp[i].opt;
        cin>>rp[i].l;
        cin>>rp[i].r;
        if(rp[i].opt==1)cin>>rp[i].v;
    }
    for(int i=1;i<=pos[n];i++){
        bl[i]=(i-1)*S+1;
        br[i]=min(i*S,n);
    }
    for(int i=1;i<=pos[n];i++){
        qcnt=0;
        for(int j=1;j<=m;j++){
            if(rp[j].opt==2)qcnt++;
            if(rp[j].l>br[i]||bl[i]>rp[j].r)continue;
            if(rp[j].opt==1){
                if(rp[j].l<=bl[i]&&br[i]<=rp[j].r)blk.AllAdd(rp[j].v);
                else blk.PartAdd(max(rp[j].l,bl[i])-bl[i]+1,min(rp[j].r,br[i])-bl[i]+1,rp[j].v);
            }
            else blk.Query(max(rp[j].l,bl[i])-bl[i]+1,min(rp[j].r,br[i])-bl[i]+1,qcnt);
        }
        //252 194
        //1 134 159
//      if(i==1)return blk.m/256/256;
        blk.bid=i;
        blk.n=br[i]-bl[i]+1;
        if(i==1||i==pos[n]){
            ptop=0;
            blk.sgt.Allocate(1,1,blk.n);
        }
        blk.Prefix();
        blk.Solve();
        blk.Clear();
//      if(i==1)return CNT/256/256;
    }
    for(int i=1;i<=qcnt;i++){
        cout<<ans[i].ansmax;
        cout << '\n';
    }
    return 0;

}