把pushdown删掉结果竟然没变。
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define INF 2147483647
#define LINF 9223372036854775807
int n,m,a[1000005],t2[1000005<<2],t3[1000005<<2],tag2[1000005<<2],tag3[1000005<<2];
void pushup(int p){
t2[p]=max(t2[p<<1],t2[p<<1|1]);
t3[p]=max(t3[p<<1],t3[p<<1|1]);
return;
}
void pushdown(int p){
if(tag2[p]){
t2[p<<1]+=tag2[p],t2[p<<1|1]+=tag2[p];
tag2[p<<1]+=tag2[p],tag2[p<<1|1]+=tag2[p];
tag2[p]=0;
}
if(tag3[p]){
t3[p<<1]+=tag3[p],t3[p<<1|1]+=tag3[p];
tag3[p<<1]+=tag3[p],tag3[p<<1|1]+=tag3[p];
tag3[p]=0;
}
return;
}
void build(int l,int r,int p){
if(l==r){
t2[p]=a[l]+a[l+1];
t3[p]=a[l]+a[l+1]+a[l+2];
return;
}
int mid=(l+r)>>1;
build(l,mid,p<<1);
build(mid+1,r,p<<1|1);
pushup(p);
return;
}
void update2(int L,int R,int l,int r,int p,int k){
if(L<=l&&r<=R){
t2[p]+=k,tag2[p]+=k;
return;
}
int mid=(l+r)>>1;
pushdown(p);
if(L<=mid) update2(L,R,l,mid,p<<1,k);
if(R>mid) update2(L,R,mid+1,r,p<<1|1,k);
pushup(p);
return;
}
void update3(int L,int R,int l,int r,int p,int k){
if(L<=l&&r<=R){
t3[p]+=k,tag3[p]+=k;
return;
}
int mid=(l+r)>>1;
pushdown(p);
if(L<=mid) update3(L,R,l,mid,p<<1,k);
if(R>mid) update3(L,R,mid+1,r,p<<1|1,k);
pushup(p);
return;
}
int query2(int L,int R,int l,int r,int p){
if(L<=l&&r<=R) return t2[p];
int mid=(l+r)>>1,ans=-LINF;
pushdown(p);
if(L<=mid) ans=max(ans,query2(L,R,l,mid,p<<1));
if(R>mid) ans=max(ans,query2(L,R,mid+1,r,p<<1|1));
return ans;
}
int query3(int L,int R,int l,int r,int p){
if(L<=l&&r<=R) return t3[p];
int mid=(l+r)>>1,ans=-LINF;
pushdown(p);
if(L<=mid) ans=max(ans,query3(L,R,l,mid,p<<1));
if(R>mid) ans=max(ans,query3(L,R,mid+1,r,p<<1|1));
return ans;
}
signed main(){
scanf("%lld%lld",&n,&m);
for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
build(1,n,1);
while(m--){
int op,l,r,x;
scanf("%lld%lld%lld",&op,&l,&r);
if(op==1){
scanf("%lld",&x);
update2(l,l,1,n,1,x),update3(l,l,1,n,1,x);
if(l<r) update2(l+1,r,1,n,1,x*2),update3(l+1,l+1,1,n,1,x*2);
if(r<n) update2(r+1,r+1,1,n,1,x),update3(r+1,r+1,1,n,1,(l==r)?x:x*2);
if(l<r-1) update3(l+2,r,1,n,1,x*3);
if(r<n-1) update3(r+2,r+2,1,n,1,x);
}
else{
int A1=query2(l+1,r,1,n,1),A2=query3(l+2,r,1,n,1),ans=0,div=0;
if(A1*3>A2*2||l+2>r) ans=A1,div=2;
else ans=A2,div=3;
if(ans%div==0) ans/=div,div=1;
printf("%lld/%lld\n",ans,div);
}
}
return 0;
}