最后一个点WA了,拍了10W组数据都没拍出结果来。
代码也找不出问题。
#include<iostream>
#include<cstdio>
#define LL long long
const int maxn=5e5+10,maxh=(1<<30)-1;
using namespace std;
int N,M,a[maxn];//lz1:maxv,lz2:l_maxv,lz3:unmaxv,lz4:l_unmaxv,maxl:max history(all lz are det)
struct node{int l,r,maxv,maxv2,maxl,cnt,lz1,lz2,lz3,lz4;LL sumv;}f[maxn<<2];
int qd(){
int ng=1,rt=0;char c=getchar();
while((c<'0'||c>'9')&&c!='-') c=getchar();
if(c=='-') ng=0,c=getchar();
while('0'<=c&&c<='9') rt=(rt<<3)+(rt<<1)+c-48,c=getchar();
return ng?rt:-rt;
}
void bin(){/*
f[t].sumv+=(r-l+1)*uv;
f[t].maxv+=uv;
if(f[t].maxv2!=-maxh) f[t].maxv2+=uv;
f[t].maxl=max(f[t].maxl,f[t].maxv);
if(l!=r){
f[t].lz1+=uv;
f[t].lz2=max(f[t].lz2,f[t].lz1);
f[t].lz3+=uv;
f[t].lz4=max(f[t].lz4,f[t].lz3);
}
f[t].sumv+=f[t].cnt*(uv-f[t].maxv);
f[t].maxv=uv;
if(l!=r) f[t].lz1=f[t].maxv-uv;
if(l<=s[p].l&
return;
非最大值的历史最大值由非最大值(次最大值)的非历史最大值加上下传下来的对非最大值的非历史最大值的历史最大增加量的更新。
*/}
void upd(int t,int ina,int inb,int inc,int ind){
f[t].sumv+=1LL*f[t].cnt*ina+1LL*(f[t].r-f[t].l+1-f[t].cnt)*inc;
f[t].maxl=max(f[t].maxl,f[t].maxv+inb);
f[t].lz2=max(f[t].lz2,f[t].lz1+inb);
f[t].lz4=max(f[t].lz4,f[t].lz3+ind);
f[t].maxv+=ina;f[t].lz1+=ina;
if(f[t].maxv2!=-maxh) f[t].maxv2+=inc;
f[t].lz3+=inc;
}
void pushup(int t){
node fl=f[t<<1],fr=f[t<<1|1];
f[t].sumv=fl.sumv+fr.sumv;
f[t].maxl=max(f[t].maxl,max(fl.maxl,fr.maxl));
f[t].maxv=max(fl.maxv,fr.maxv);
f[t].cnt=0;
if(f[t].maxv==fl.maxv) f[t].cnt+=fl.cnt,fl.maxv=-maxh;
if(f[t].maxv==fr.maxv) f[t].cnt+=fr.cnt,fr.maxv=-maxh;
f[t].maxv2=max(max(fl.maxv,fr.maxv),max(fl.maxv2,fr.maxv2));
}
void pushdown(int t){
int maxxv=max(f[t<<1].maxv,f[t<<1|1].maxv);
if(maxxv==f[t<<1].maxv) upd(t<<1,f[t].lz1,f[t].lz2,f[t].lz3,f[t].lz4);
else upd(t<<1,f[t].lz3,f[t].lz4,f[t].lz3,f[t].lz4);
if(maxxv==f[t<<1|1].maxv) upd(t<<1|1,f[t].lz1,f[t].lz2,f[t].lz3,f[t].lz4);
else upd(t<<1|1,f[t].lz3,f[t].lz4,f[t].lz3,f[t].lz4);
f[t].lz1=f[t].lz2=f[t].lz3=f[t].lz4=0;
}
void build(int t,int l,int r){
f[t].l=l,f[t].r=r;
if(l==r){
f[t].maxl=f[t].maxv=f[t].sumv=a[l];
f[t].maxv2=-maxh;
f[t].cnt=1;
return;
}
int m=(l+r)/2;
build(t<<1,l,m);build(t<<1|1,m+1,r);
pushup(t);
}
void change1(int t,int ul,int ur,int uv){
int l=f[t].l,r=f[t].r;
if(ul<=l&&r<=ur) return upd(t,uv,uv,uv,uv);
int m=(l+r)/2;
pushdown(t);
if(m>=ul) change1(t<<1,ul,ur,uv);
if(m<ur) change1(t<<1|1,ul,ur,uv);
pushup(t);
}
void change2(int t,int ul,int ur,int uv){
int l=f[t].l,r=f[t].r;
if(f[t].maxv<=uv) return;
if(ul<=l&&r<=ur&&f[t].maxv2<=uv) return upd(t,uv-f[t].maxv,0,0,0);
pushdown(t);
int m=(l+r)/2;
if(m>=ul) change2(t<<1,ul,ur,uv);
if(m<ur) change2(t<<1|1,ul,ur,uv);
pushup(t);
}
LL ask3(int t,int ul,int ur){
int l=f[t].l,r=f[t].r;
if(ul<=l&&r<=ur) return f[t].sumv;
int m=(l+r)/2;LL rt=0;
pushdown(t);
if(m>=ul) rt+=ask3(t<<1,ul,ur);
if(m<ur) rt+=ask3(t<<1|1,ul,ur);
return rt;
}
int ask4(int t,int ul,int ur){
int l=f[t].l,r=f[t].r;
if(ul<=l&&r<=ur) return f[t].maxv;
int m=(l+r)/2,rt=-maxh;
pushdown(t);
if(m>=ul) rt=ask4(t<<1,ul,ur);
if(m<ur) rt=max(rt,ask4(t<<1|1,ul,ur));
return rt;
}
int ask5(int t,int ul,int ur){
int l=f[t].l,r=f[t].r;
if(ul<=l&&r<=ur) return f[t].maxl;
int m=(l+r)/2,rt=-maxh;
pushdown(t);
if(m>=ul) rt=ask5(t<<1,ul,ur);
if(m<ur) rt=max(rt,ask5(t<<1|1,ul,ur));
return rt;
}
int main(){
N=qd(),M=qd();
for(int i=1;i<=N;i++) a[i]=qd();
build(1,1,N);
while(M--){
int ina=qd();
if(ina<=2){
int inb=qd(),inc=qd(),ind=qd();
if(ina==1) change1(1,inb,inc,ind);
else change2(1,inb,inc,ind);
}
else{
int inb=qd(),inc=qd();
if(ina==3) printf("%lld\n",ask3(1,inb,inc));
else if(ina==4) printf("%d\n",ask4(1,inb,inc));
else printf("%d\n",ask5(1,inb,inc));
}
}
return 0;
}
//1->3,1->4,1->5;2->3,2->4;