huangqirui123 @ 2023-08-16 21:37:22

by OldDriverTree @ 2023-08-16 21:42:05

@huangqirui123 看题解

by huangqirui123 @ 2023-08-16 21:43:43

@OldDriverTree tle

by OldDriverTree @ 2023-08-16 21:52:34

@huangqirui123 你不发代码我怎么知道你代码哪错了？

by Zq_water @ 2023-08-16 22:01:33

@huangqirui123 你该不会用了暴力吧

by OldDriverTree @ 2023-08-16 22:07:09

lz 疑似抄题解，2 min 写了 23 KB 代码？

by huangqirui123 @ 2023-08-16 22:09:39

啥东东？？？

by huangqirui123 @ 2023-08-16 22:10:33

@Zq_water 没有

by OldDriverTree @ 2023-08-16 22:11:47

@huangqirui123 发下代码

by Zq_water @ 2023-08-16 22:12:26

你写的是分块还是啥

by huangqirui123 @ 2023-08-16 22:14:41

define got(x,len) (((x)-1)/(len)+1)

define LB(x,len) (((x)-1)*(len)+1)

define RB(x,len) min(((x)*(len)),n)

struct Question{ int op=0,lft=0,rgt=0; long long v=0; }que[maxn]; namespace KamisatoAyaka{ int blk[maxn/maxs+5],brgt[maxn/maxs+5],pos[maxn],tot; struct Point{ long long x,y; inline Point operator+(register const Point &b)const{ return{x+b.x,y+b.y}; } inline Point operator-(register const Point &b)const{ return{x-b.x,y-b.y}; } inline bool operator <=(register const Point &b)const{ return xb.y>=yb.x; } } pool[maxn]; struct Hull{ Point pnt; int siz,mxpnt; long long tag; inline Point operator [](register const int x){ return{pnt[x].x,pnt[x].y+tagpnt[x].x}; } inline void insert(register Point x){ pnt[x.x].y=max(pnt[x.x].y,x.y); } inline void pushBack(register Point x){ pnt[siz++]=x; } inline void init(register int len){ pnt[0]={0,0},siz=len+1,tag=0; for(register int i=1;i<=len;++i) pnt[i]={i,-inf}; } inline void Jarvis(){ if(siz<=2) return; int top=1; for(register int i=2;i<siz;++i){ if(pnt[i].y==-inf) continue; while(top>=1&&(pnt[top]-pnt[top-1]) <=(pnt[i]-pnt[top-1])) --top; pnt[++top]=pnt[i]; } siz=top+1,tag=0; } inline bool check(register int x,register long long addv){ return(pnt[x+1].x-pnt[x].x)(tag+addv)+pnt[x+1].y-pnt[x].y>0; } inline long long Maxv(register long long addv){ while(mxpnt<siz-1&&check(mxpnt,addv)) ++mxpnt; return pnt[mxpnt].x(tag+addv)+pnt[mxpnt].y; } inline long long MaxvBS(register long long addv){ register int lft=-1,rgt=siz-1,mid; for(mid=lft+rgt>>1;lft<rgt-1;mid=lft+rgt>>1) if(check(mid,addv)) lft=mid; else rgt=mid; mxpnt=rgt; return pnt[mxpnt].x(tag+addv)+pnt[mxpnt].y; } }; struct AyakaNode{ long long lmax,rmax,midmax,sum; inline AyakaNode operator+(const AyakaNode &b)const{ return{max(lmax,sum+b.lmax),max(rmax+b.sum,b.rmax),max(max(midmax,b.midmax),rmax+b.lmax),sum+b.sum}; } } res[maxn]; struct LineTree{ Hull lmax[maxs<<2],rmax[maxs<<2],midmax[maxs<<2]; long long sum[maxs<<2],tag[maxs<<2]; inline void init(register int rt,register int lft,register int rgt){ lmax[rt].pnt=pool+tot; tot+=rgt-lft+3; rmax[rt].pnt=pool+tot; tot+=rgt-lft+3; midmax[rt].pnt=pool+tot; tot+=rgt-lft+3; if(lft==rgt) return; int mid=(lft+rgt)>>1; init(rt<<1,lft,mid); init(rt<<1|1,mid+1,rgt); } inline void preSufMerge(register Hull &c,register Hull &a,register Hull &b,register Point addb){ for(register int i=0,t=a.siz;i<t;++i) c.pushBack(a[i]); for(register int i=0,t=b.siz;i<t;++i) c.pushBack(addb+b[i]); c.Jarvis(); } inline void Minkowski(register Hull &c,register Hull &a,register Hull &b){ int i=0,j=0,sa=a.siz-1,sb=b.siz-1; for(c.insert(a[i]+b[j]);i<sa&&j<sb;c.insert(a[i]+b[j])) a[i+1]-a[i]<=b[j+1]-b[j]?++j:++i; while(i<sa) c.insert(a[++i]+b[j]); while(j<sb) c.insert(a[i]+b[++j]); } inline void pushUp(register int rt,register int lft,register int rgt){ int mid=(lft+rgt)>>1; preSufMerge(lmax[rt],lmax[rt<<1],lmax[rt<<1|1],{mid-lft+1,sum[rt<<1]}); preSufMerge(rmax[rt],rmax[rt<<1|1],rmax[rt<<1],{rgt-mid,sum[rt<<1|1]}); midmax[rt].init(rgt-lft+1); for(register int i=0,t=midmax[rt<<1].siz;i<t;++i) midmax[rt].insert(midmax[rt<<1][i]); for(register int i=0,t=midmax[rt<<1|1].siz;i<t;++i) midmax[rt].insert(midmax[rt<<1|1][i]); Minkowski(midmax[rt],rmax[rt<<1],lmax[rt<<1|1]); midmax[rt].Jarvis(); lmax[rt].mxpnt=rmax[rt].mxpnt=midmax[rt].mxpnt=0; sum[rt]=sum[rt<<1]+sum[rt<<1|1]; } inline void add(register int rt,register int lft,register int rgt,register long long d){ tag[rt]+=d; lmax[rt].tag+=d; rmax[rt].tag+=d; midmax[rt].tag+=d; sum[rt]+=d(rgt-lft+1); } inline void pushDown(register int rt,register int lft,register int rgt){ if(lft==rgt||!tag[rt]) return; int mid=(lft+rgt)>>1; add(rt<<1,lft,mid,tag[rt]); add(rt<<1|1,mid+1,rgt,tag[rt]); tag[rt]=0; } inline void buildTree(register int rt,register int lft,register int rgt,register int bid){ if(lft==rgt){ sum[rt]=a[lft+blk[bid]-1]; lmax[rt].pushBack({0,0}); lmax[rt].pushBack({1,sum[rt]}); rmax[rt].pushBack({0,0}); rmax[rt].pushBack({1,sum[rt]}); midmax[rt].pushBack({0,0}); midmax[rt].pushBack({1,sum[rt]}); return; } int mid=(lft+rgt)>>1; buildTree(rt<<1,lft,mid,bid); buildTree(rt<<1|1,mid+1,rgt,bid); pushUp(rt,lft,rgt); } inline void clear(register int rt,register int lft,register int rgt){ lmax[rt].siz=rmax[rt].siz=midmax[rt].siz=0; lmax[rt].mxpnt=rmax[rt].mxpnt=midmax[rt].mxpnt=0; lmax[rt].tag=rmax[rt].tag=midmax[rt].tag=0; tag[rt]=0; if(lft==rgt) return; int mid=(lft+rgt)>>1; clear(rt<<1,lft,mid); clear(rt<<1|1,mid+1,rgt); } inline void change(register int rt,register int lft,register int rgt,register int l,register int r,register long long d){ if(lft==l&&rgt==r) return add(rt,lft,rgt,d); pushDown(rt,lft,rgt); int mid=(lft+rgt)>>1; if(r<=mid) change(rt<<1,lft,mid,l,r,d); else if(l>mid) change(rt<<1|1,mid+1,rgt,l,r,d); else change(rt<<1,lft,mid,l,mid,d),change(rt<<1|1,mid+1,rgt,mid+1,r,d); lmax[rt].siz=rmax[rt].siz=midmax[rt].siz=0; pushUp(rt,lft,rgt); } inline AyakaNode query(register int lft,register int rgt,register long long addv){ return{lmax[1].Maxv(addv),rmax[1].Maxv(addv),midmax[1].Maxv(addv),sum[1]+(rgt-lft+1)addv}; } inline AyakaNode ask(register int rt,register int lft,register int rgt,register int l,register int r,register long long addv){ if(lft==l&&rgt==r) return rt==1?query(l,r,addv):(AyakaNode){lmax[rt].MaxvBS(addv),rmax[rt].MaxvBS(addv),midmax[rt].MaxvBS(addv),sum[rt]+(r-l+1)addv}; pushDown(rt,lft,rgt); register int mid=(lft+rgt)>>1; if(r<=mid) return ask(rt<<1,lft,mid,l,r,addv); else if(l>mid) return ask(rt<<1|1,mid+1,rgt,l,r,addv); else return ask(rt<<1,lft,mid,l,mid,addv)+ask(rt<<1|1,mid+1,rgt,mid+1,r,addv); } }; struct QuestionForBlock{ int lft=0,rgt=0,id=0; long long v=0,typ=0; inline bool operator<(register const QuestionForBlock &b)const{ return v<b.v; } }; struct Block{ LineTree ayaka; int bid,bn,bm,cnt[maxr]; QuestionForBlock neq[maxn],tmp[maxn]; long long tag,valt[maxn],val[maxn]; inline void update(register long long d){ tag+=d; } inline void change(register int lft,register int rgt,register long long d){ if(d==0) return; if(lft==1&&rgt==bn) return tag+=d,void(); neq[bm++]={lft,rgt,0,tag,d}; } inline void query(register int lft,register int rgt,register int id){ neq[bm++]={lft,rgt,id,tag,0}; }

define geted(x,d)(((x)>>((d)*bit))&(maxr-1))

    inline void radixSort(register int lft,register int rgt){
        if(rgt-lft<=1500) 
            return sort(neq+lft,neq+rgt),void();
        register long long *x=val,*y=valt;
        register int tt=rgt-lft;
        for(register int i=lft;i<rgt;++i) 
            x[i-lft]=y[i-lft]=neq[i].v|((1ll*i)<<35);
        for(register int d=0;d<4;++d){
            for(register int i=0;i<maxr;++i) 
                cnt[i]=0;
            for(register int i=0;i<tt;++i) 
                ++cnt[geted(x[i],d)];
            for(register int i=1;i<maxr;++i) 
                cnt[i]+=cnt[i-1];
            for(register int i=tt-1;i>=0;--i)
                 y[--cnt[geted(x[i],d)]]=x[i];
            swap(x,y);
        }
        for(register int i=lft;i<rgt;++i) 
            tmp[i-lft]=neq[i];
        for(register int i=lft;i<rgt;++i) 
            neq[i]=tmp[(x[i-lft]>>35)-lft];
    }
    inline void init(){
        register long long mintag=0;
        for(register int i=0;i<bm;++i) 
            mintag=min(mintag,neq[i].v);
        for(register int i=0;i<bm;++i) 
            neq[i].v-=mintag;
        for(register int i=blk[bid],t=brgt[bid];i<=t;++i) 
            a[i]+=mintag;
        ayaka.buildTree(1,1,bn,bid);
        register int last=0;
        for(register int i=0;i<bm;++i)
            if(neq[i].typ){
                if(i!=last)
                    radixSort(last,i);
                last=i+1;
        }
        if(last!=bm) 
            radixSort(last,bm);
    }
    inline void solve(){
        for(register int i=0;i<bm;++i)
            if(!neq[i].typ){
                if(i&&neq[i-1].typ){
                    ayaka.lmax[1].MaxvBS(neq[i].v);
                    ayaka.rmax[1].MaxvBS(neq[i].v);
                    ayaka.midmax[1].MaxvBS(neq[i].v);
                }
                res[neq[i].id]=res[neq[i].id]+ayaka.ask(1,1,bn,neq[i].lft,neq[i].rgt,neq[i].v);
            }
            else 
                ayaka.change(1,1,bn,neq[i].lft,neq[i].rgt,neq[i].typ);
    }
    inline void clear(){
        bm=tag=0;
        ayaka.clear(1,1,bn);
    }
} ayk;
inline void work(){  
    register int qcnt;
    for(register int i=1;i<=n;++i) 
        pos[i]=got(i,maxs);
    for(register int i=1;i<=pos[n];++i){
        blk[i]=LB(i,maxs);
        brgt[i]=RB(i,maxs);
    }
    for(register int i=1;i<=pos[n];++i){
        qcnt=0;
        for(register int j=1;j<=m;++j){
            if(que[j].op==2)
                ++qcnt;
            if(que[j].lft>brgt[i]||que[j].rgt<blk[i])
                continue;
            if(que[j].op==1){
                if(que[j].lft<=blk[i]&&que[j].rgt>=brgt[i]) 
                    ayk.update(que[j].v);
                else 
                    ayk.change(max(que[j].lft,blk[i])-blk[i]+1,min(que[j].rgt,brgt[i])-blk[i]+1,que[j].v);
            }
            else 
                ayk.query(max(que[j].lft,blk[i])-blk[i]+1,min(que[j].rgt,brgt[i])-blk[i]+1,qcnt);
        }
        ayk.bid=i;
        ayk.bn=brgt[i]-blk[i]+1;
        if(i==1||i==pos[n])
            tot=0,ayk.ayaka.init(1,1,ayk.bn);
        ayk.init();
        ayk.solve();
        ayk.clear();
    }
    for(register int i=1;i<=qcnt;++i)
        quickWrite(res[i].midmax,'\n');
}

} namespace AetherKamisatoAyaka{ long long check[100001],nowu,cnt1,cnt2,c[100001],qf[100001]; bool check1,hmz; inline void add(register long long now,register long long v){ for(;now<=n;now+=now & -now) c[now]+=v; } inline long long sum(register long long tmp){ register long long s=0; for(;tmp>0;tmp -= tmp & -tmp) s+=c[tmp]; return s; } inline void getMid(register long long pos,register long long lft,register long long rgt,register bool vis); inline void getMid1(register long long pos,register long long lft,register long long rgt,register bool vis); inline void getMid2(register long long pos,register long long lft,register long long rgt,register bool vis); inline void getMin(register long long pos,register long long lft,register long long rgt); namespace Ayakawork1{ struct Node{ long long lft,rgt,mid,sum,maxx,minn,tag; bool need; Node(register long long lft=0,register long long rgt=0,register long long mid=0,register long long sum=0,register long long maxx=0,register long long minn=0,register long long tag=0):lft(lft),rgt(rgt),mid(mid),sum(sum),maxx(maxx),minn(minn),tag(tag){need=0;} } tree[262144]; inline Node merge(register Node x,register Node y){ return Node(max(x.lft,x.sum+y.lft),max(y.rgt,y.sum+x.rgt),max(max(x.mid,y.mid),x.rgt+y.lft),x.sum+y.sum,max(x.maxx,y.maxx),min(x.minn,y.minn),0ll); } inline void pushDown(register long long now,register long long lft,register long long rgt){ register long long mid=(lft+rgt)>>1; if(tree[now].tag!=0){ long long mid=(lft+rgt)>>1; tree[now<<1].sum +=(mid-lft+1)tree[now].tag; tree[now<<1|1].sum +=(rgt-mid)tree[now].tag; tree[now<<1].tag+=tree[now].tag; tree[now<<1|1].tag+=tree[now].tag; tree[now<<1].maxx+=tree[now].tag; tree[now<<1|1].maxx+=tree[now].tag; tree[now<<1].minn+=tree[now].tag; tree[now<<1|1].minn+=tree[now].tag; tree[now<<1].lft=tree[now<<1].rgt=tree[now<<1].mid=max(tree[now<<1].sum,0ll); tree[now<<1|1].lft=tree[now<<1|1].rgt=tree[now<<1|1].mid=max(tree[now<<1|1].sum,0ll); tree[now].tag=0; } if(tree[now].need&&lft!=rgt){ tree[now<<1].need=true; tree[now<<1|1].need=true; getMid(now<<1,lft,mid,true); getMid(now<<1|1,mid+1,rgt,true); tree[now].need=false; } } inline void buildTree(register long long now,register long long lft,register long long rgt){ if(lft==rgt){ tree[now].need=false; tree[now].lft=tree[now].rgt=tree[now].mid=max(a[lft],0ll); tree[now].sum=tree[now].minn=tree[now].maxx=a[lft]; tree[now].tag=0; return; } tree[now].need=false; register long long mid=(lft+rgt)>>1; buildTree(now<<1,lft,mid),buildTree(now<<1|1,mid+1,rgt); tree[now]=merge(tree[now<<1],tree[now<<1|1]); } inline void update(register long long now,register long long lft,register long long rgt,register long long x,register long long y,register long long w){ if(lft>y||rgt<x) return; if(x<=lft&&rgt<=y){ if(tree[now].maxx+w<=0||tree[now].minn+w>=0){ tree[now].sum +=(rgt-lft+1)w; tree[now].tag+=w; tree[now].maxx+=w; tree[now].minn+=w; tree[now].lft=tree[now].rgt=tree[now].mid=max(tree[now].sum,0ll); tree[now].need=false; return; } else if((!check1&&rgt-lft+1<=500) ||(check1&&rgt-lft+1<=5000)){ tree[now].sum +=(rgt-lft+1)w; tree[now].tag+=w; tree[now].maxx+=w; tree[now].minn+=w; tree[now].need=true; getMid(now,lft,rgt,true); return; } } if(rgt-lft+1<=500){ getMin(now,lft,rgt); if(tree[now].maxx<=0||tree[now].minn>=0) tree[now].mid=tree[now].lft=tree[now].rgt=max(0ll,tree[now].sum); else getMid(now,lft,rgt,true); return; } pushDown(now,lft,rgt); register long long mid=(lft+rgt)>>1; update(now<<1,lft,mid,x,y,w); update(now<<1|1,mid+1,rgt,x,y,w); tree[now]=merge(tree[now<<1],tree[now<<1|1]); } inline Node query(register long long now,register long long lft,register long long rgt,register long long x,register long long y){ if(x<=lft&&rgt<=y) return tree[now]; if(lft<=x&&rgt<=y&&(rgt-x+1)<=700&&(tree[now].need||rgt-x<=500)) return getMid(0,x,rgt,true),tree[0]; if(lft>=x&&rgt>=y&&(y-lft+1)<=700&&(tree[now].need||y-lft<=500)) return getMid(0,lft,y,true),tree[0]; register long long mid=(lft+rgt)>>1; pushDown(now,lft,rgt); Node res; if(x>mid) res=query(now<<1|1,mid+1,rgt,x,y); else if(y<=mid) res=query(now<<1,lft,mid,x,y); else { Node resa=query(now<<1,lft,mid,x,y),resb=query(now<<1|1,mid+1,rgt,x,y); res=Node(max(resa.lft,resa.sum+resb.lft),max(resb.rgt,resb.sum+resa.rgt),max(resa.mid,max(resb.mid,resa.rgt+resb.lft)),resa.sum+resb.sum,0ll,0ll,0ll); } tree[now]=merge(tree[now<<1],tree[now<<1|1]); return res; } } namespace Ayakawork2{ long long eps; struct Node{ long long lft,rgt,mid,sum,maxx,minn,tag; bool check; } tree[262144]; inline bool get(register Node now,register long long len){ return(now.maxx<=0||now.minn>=0); } inline void pushDown(register long long now,register long long lft,register long long rgt){ long long mid=(lft+rgt)>>1; tree[now<<1].sum+=(mid-lft+1)tree[now].tag, tree[now<<1|1].sum+=(rgt-mid)tree[now].tag; tree[now<<1].tag+=tree[now].tag, tree[now<<1|1].tag+=tree[now].tag; tree[now<<1].maxx+=tree[now].tag, tree[now<<1|1].maxx+=tree[now].tag; tree[now<<1].minn+=tree[now].tag, tree[now<<1|1].minn+=tree[now].tag; tree[now<<1].check=get(tree[now<<1],mid-lft+1); tree[now<<1|1].check=get(tree[now<<1|1],rgt-mid); tree[now].tag=0; } inline Node merge(register Node x,register Node y,register long long len){ Node res={max(x.lft,x.sum+y.lft),max(y.rgt,y.sum+x.rgt),max(max(x.mid,y.mid),x.rgt+y.lft),x.sum+y.sum,max(x.maxx,y.maxx),min(x.minn,y.minn)}; if(x.check||y.check) res.check=true; else res.check=false; return res; } inline void buildTree(register long long now,register long long lft,register long long rgt){ tree[now].tag=0; tree[now].check=false; if(lft==rgt){ tree[now].maxx=tree[now].minn=tree[now].sum=a[lft]; return; } register long long mid=(lft+rgt)>>1; buildTree(now<<1,lft,mid); buildTree(now<<1|1,mid+1,rgt); tree[now]=merge(tree[now<<1],tree[now<<1|1],rgt-lft+1); } inline void update(register long long now,register long long lft,register long long rgt,register long long x,register long long y,register long long w){ if(lft>y||rgt<x) return; if(x<=lft&&rgt<=y){ tree[now].sum +=(rgt-lft+1)*w; tree[now].maxx+=w; tree[now].minn+=w; tree[now].tag+=w; if((tree[now].maxx<=0||tree[now].minn>=0)&&rgt-lft+1>=eps) tree[now].check=true; else tree[now].check=false; return; } pushDown(now,lft,rgt); register long long mid=(lft+rgt)>>1; update(now<<1,lft,mid,x,y,w); update(now<<1|1,mid+1,rgt,x,y,w); tree[now]=merge(tree[now<<1],tree[now<<1|1],rgt-lft+1); } inline Node query(register long long now,register long long lft,register long long rgt,register long long x,register long long y){ tree[now].check=get(tree[now],rgt-lft+1); if(lft>y||rgt<x) return Node{-10000000,-10000000,-10000000,0,0,0,0,0}; if(x<=lft&&rgt<=y){ if(tree[now].maxx<=0||tree[now].minn>=0){ tree[now].lft=tree[now].rgt=tree[now].mid=max(tree[now].sum,0ll); return tree[now]; } else if(rgt-lft+1<=300){ getMid(now,lft,rgt,false); return tree[now]; } } Node res; pushDown(now,lft,rgt); register long long mid=(lft+rgt)>>1; if(lft>mid) res=query(now<<1,lft,mid,x,y); else if(rgt<=mid) res=query(now<<1|1,mid+1,rgt,x,y); else{ Node a=query(now<<1,lft,mid,x,y),b=query(now<<1|1,mid+1,rgt,x,y); res={max(a.lft,a.sum+b.lft),max(b.rgt,b.sum+a.rgt),max(max(a.mid,b.mid),a.rgt+b.lft),a.sum+b.sum,max(a.maxx,b.maxx),min(a.minn,b.minn)}; } tree[now]=merge(tree[now<<1],tree[now<<1|1],rgt-lft+1); return res; } } inline void work(){ register long long lft,rgt,w; for(register long long i=1;i<=n;++i) qf[i]=a[i]-a[i-1],add(i,qf[i]); Ayakawork1::buildTree(1,1,n); for(register long long k=1;k<=m;++k){ lft=que[k].lft; rgt=que[k].rgt; w=que[k].v; if(!lft) ++lft; nowu=lft; if(!hmz){ if(que[k].op==1){ qf[lft]+=w; qf[rgt+1]-=w; add(lft,w); add(rgt+1,-w); Ayakawork1::update(1,1,n,que[k].lft,que[k].rgt,que[k].v); } else{ if(rgt-lft+1<=50000){ register long long res=0,now=0,qlft=sum(lft),i; for(i=lft;i<=rgt-11;i+=12){ now=(now<0?0:now)+qlft; res=(res>now?res:now); qlft+=qf[i+1]; now=(now<0?0:now)+qlft; res=(res>now?res:now); qlft+=qf[i+2]; now=(now<0?0:now)+qlft; res=(res>now?res:now); qlft+=qf[i+3]; now=(now<0?0:now)+qlft; res=(res>now?res:now); qlft+=qf[i+4]; now=(now<0?0:now)+qlft; res=(res>now?res:now); qlft+=qf[i+5]; now=(now<0?0:now)+qlft; res=(res>now?res:now); qlft+=qf[i+6]; now=(now<0?0:now)+qlft; res=(res>now?res:now); qlft+=qf[i+7]; now=(now<0?0:now)+qlft; res=(res>now?res:now); qlft+=qf[i+8]; now=(now<0?0:now)+qlft; res=(res>now?res:now); qlft+=qf[i+9]; now=(now<0?0:now)+qlft; res=(res>now?res:now); qlft+=qf[i+10]; now=(now<0?0:now)+qlft; res=(res>now?res:now); qlft+=qf[i+11]; now=(now<0?0:now)+qlft; res=(res>now?res:now); qlft+=qf[i+12]; } while(i<=rgt){ now=(now<0?0:now)+qlft; res=(res>now?res:now); qlft+=qf[++i]; } quickWrite(res,'\n'); } else quickWrite(Ayakawork1::query(1,1,n,que[k].lft,que[k].rgt).mid,'\n'); } } } } inline void getMid(register long long pos,register long long lft,register long long rgt,register bool vis){ if(!pos||!vis||!check1 ||(lft!=nowu&&Ayakawork1::tree[pos].maxx>=1e8+1e5)) getMid1(pos,lft,rgt,vis); else getMid2(pos,lft,rgt,vis); } inline void getMid1(register long long pos,register long long lft,register long long rgt,register bool vis){ register long long res[3]={0,0,0},now[3]={0,0,0},qlft=sum(lft),i; for(i=lft;i<=rgt-3;i+=4){ now[1]+=qlft; res[1]=(res[1]>now[1]?res[1]:now[1]); now[2]=(now[2]<0?0:now[2])+qlft; qlft+=qf[i+1]; res[2]=(res[2]>now[2]?res[2]:now[2]); now[1]+=qlft; res[1]=(res[1]>now[1]?res[1]:now[1]); now[2]=(now[2]<0?0:now[2])+qlft; qlft+=qf[i+2]; res[2]=(res[2]>now[2]?res[2]:now[2]); now[1]+=qlft; res[1]=(res[1]>now[1]?res[1]:now[1]); now[2]=(now[2]<0?0:now[2])+qlft; qlft+=qf[i+3]; res[2]=(res[2]>now[2]?res[2]:now[2]); now[1]+=qlft; res[1]=(res[1]>now[1]?res[1]:now[1]); now[2]=(now[2]<0?0:now[2])+qlft; qlft+=qf[i+4]; res[2]=(res[2]>now[2]?res[2]:now[2]); } while(i<=rgt){ now[1]+=qlft; res[1]=(res[1]>now[1]?res[1]:now[1]); now[2]=(now[2]<0?0:now[2])+qlft; qlft+=qf[i+1]; res[2]=(res[2]>now[2]?res[2]:now[2]); ++i; } if(vis){ Ayakawork1::tree[pos].lft=res[1]; Ayakawork1::tree[pos].rgt=now[2]; Ayakawork1::tree[pos].mid=res[2]; } else{ Ayakawork2::tree[pos].lft=res[1]; Ayakawork2::tree[pos].rgt=now[2]; Ayakawork2::tree[pos].mid=res[2]; } } inline void getMid2(register long long pos,register long long lft,register long long rgt,register bool vis){ register long long now[3]={0,0,0},qlft=sum(lft),i,res[3]={0,0,0}; for(i=lft;i<=rgt-12;i+=13){ now[2]=(now[2]<0?0:now[2])+qlft; qlft+=qf[i+1]; res[2]=(res[2]>now[2]?res[2]:now[2]); now[2]=(now[2]<0?0:now[2])+qlft; qlft+=qf[i+2]; res[2]=(res[2]>now[2]?res[2]:now[2]); now[2]=(now[2]<0?0:now[2])+qlft; qlft+=qf[i+3]; res[2]=(res[2]>now[2]?res[2]:now[2]); now[2]=(now[2]<0?0:now[2])+qlft; qlft+=qf[i+4]; res[2]=(res[2]>now[2]?res[2]:now[2]); now[2]=(now[2]<0?0:now[2])+qlft; qlft+=qf[i+5]; res[2]=(res[2]>now[2]?res[2]:now[2]); now[2]=(now[2]<0?0:now[2])+qlft; qlft+=qf[i+6]; res[2]=(res[2]>now[2]?res[2]:now[2]); now[2]=(now[2]<0?0:now[2])+qlft; qlft+=qf[i+7]; res[2]=(res[2]>now[2]?res[2]:now[2]); now[2]=(now[2]<0?0:now[2])+qlft; qlft+=qf[i+8]; res[2]=(res[2]>now[2]?res[2]:now[2]); now[2]=(now[2]<0?0:now[2])+qlft; qlft+=qf[i+9]; res[2]=(res[2]>now[2]?res[2]:now[2]); now[2]=(now[2]<0?0:now[2])+qlft; qlft+=qf[i+10]; res[2]=(res[2]>now[2]?res[2]:now[2]); now[2]=(now[2]<0?0:now[2])+qlft; qlft+=qf[i+11]; res[2]=(res[2]>now[2]?res[2]:now[2]); now[2]=(now[2]<0?0:now[2])+qlft; qlft+=qf[i+12]; res[2]=(res[2]>now[2]?res[2]:now[2]); now[2]=(now[2]<0?0:now[2])+qlft; qlft+=qf[i+13]; res[2]=(res[2]>now[2]?res[2]:now[2]); } while(i<=rgt){ now[2]=(now[2]<0?0:now[2])+qlft; qlft+=qf[i+1]; res[2]=(res[2]>now[2]?res[2]:now[2]), ++i; } if(vis){ Ayakawork1::tree[pos].lft=res[1]; Ayakawork1::tree[pos].rgt=now[2]; Ayakawork1::tree[pos].mid=res[2]; } else{ Ayakawork2::tree[pos].lft=res[1]; Ayakawork2::tree[pos].rgt=now[2]; Ayakawork2::tree[pos].mid=res[2]; } } inline void getMin(register long long pos,register long long lft,register long long rgt){ register long long i,sm=0,maxx=-1e10,minn=1e10,qlft=sum(lft); for(i=lft;i<=rgt-11;i+=12){ sm+=qlft; maxx=(maxx<qlft?qlft:maxx); minn=(minn<qlft?minn:qlft); qlft+=qf[i+1]; sm+=qlft; maxx=(maxx<qlft?qlft:maxx); minn=(minn<qlft?minn:qlft); qlft+=qf[i+2]; sm+=qlft; maxx=(maxx<qlft?qlft:maxx); minn=(minn<qlft?minn:qlft); qlft+=qf[i+3]; sm+=qlft; maxx=(maxx<qlft?qlft:maxx); minn=(minn<qlft?minn:qlft); qlft+=qf[i+4]; sm+=qlft; maxx=(maxx<qlft?qlft:maxx); minn=(minn<qlft?minn:qlft); qlft+=qf[i+5]; sm+=qlft; maxx=(maxx<qlft?qlft:maxx); minn=(minn<qlft?minn:qlft); qlft+=qf[i+6]; sm+=qlft; maxx=(maxx<qlft?qlft:maxx); minn=(minn<qlft?minn:qlft); qlft+=qf[i+7]; sm+=qlft; maxx=(maxx<qlft?qlft:maxx); minn=(minn<qlft?minn:qlft); qlft+=qf[i+8]; sm+=qlft; maxx=(maxx<qlft?qlft:maxx); minn=(minn<qlft?minn:qlft); qlft+=qf[i+9]; sm+=qlft; maxx=(maxx<qlft?qlft:maxx); minn=(minn<qlft?minn:qlft); qlft+=qf[i+10]; sm+=qlft;maxx=(maxx<qlft?qlft:maxx); minn=(minn<qlft?minn:qlft); qlft+=qf[i+11]; sm+=qlft;maxx=(maxx<qlft?qlft:maxx); minn=(minn<qlft?minn:qlft); qlft+=qf[i+12]; } while(i<=rgt){ sm+=qlft; maxx=(maxx<qlft?qlft:maxx); minn=(minn<qlft?minn:qlft); qlft+=qf[++i]; } Ayakawork1::tree[pos].sum=sm; Ayakawork1::tree[pos].maxx=maxx; Ayakawork1::tree[pos].minn=minn; } }