由乃求调,悬赏奇数个关注
查看原帖
由乃求调,悬赏奇数个关注
1374349
wangkaiwei楼主2025/8/30 10:40

把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;
}
2025/8/30 10:40
加载中...