P6242线段树3求调

我发现即使不修改，就增加几次查询操作，原来的值就变了，这说明应该是push up或者push down的问题……

#include<bits/stdc++.h>
#define ls (id<<1)
#define rs (id<<1|1)
using namespace std;
const int maxn=5e5+5;
int n,q;
long long a[maxn];
struct node{
	int l,r,len,mx_num;
	long long mx,sec,sum;
	long long add_mx,add_mx_mx,his_mx_mx,add_unmx,add_unmx_mx;
}tr[maxn<<2];
void push_up(int id){
	tr[id].mx=max(tr[ls].mx,tr[rs].mx);
	if(tr[ls].mx==tr[rs].mx){
		tr[id].mx_num=tr[ls].mx_num+tr[rs].mx_num;
		tr[id].sec=max(tr[ls].sec,tr[rs].sec);
	}else{
		if(tr[ls].mx>tr[rs].mx){
			tr[id].mx_num=tr[ls].mx_num;
		}else{
			tr[id].mx_num=tr[rs].mx_num;
		}tr[id].sec=max(max(tr[ls].sec,tr[rs].sec),min(tr[ls].mx,tr[rs].mx));
	}tr[id].sum=tr[ls].sum+tr[rs].sum;
	tr[id].his_mx_mx=max(tr[ls].his_mx_mx,tr[rs].his_mx_mx);
}void add_tag(int id,long long add1,long long add2,long long add3,long long add4){
	tr[id].sum+=add1*tr[id].mx_num+add2*(tr[id].len-tr[id].mx_num);
	tr[id].his_mx_mx=max(tr[id].his_mx_mx,tr[id].mx+add3);
	tr[id].mx+=add1;
	if(tr[id].sec!=-1e18){
		tr[id].sec+=add2;
	}tr[id].add_mx_mx=max(tr[id].add_mx_mx,tr[id].add_mx+add3);
	tr[id].add_unmx_mx=max(tr[id].add_unmx_mx,tr[id].add_unmx+add4);
	tr[id].add_mx+=add1;
	tr[id].add_unmx+=add2;
}void push_down(int id){
	long long mx=max(tr[ls].mx,tr[rs].mx);
	if(tr[ls].mx==mx){
		add_tag(ls,tr[id].add_mx,tr[id].add_mx_mx,tr[id].add_unmx,tr[id].add_unmx_mx);
	}else{
		add_tag(ls,tr[id].add_mx_mx,tr[id].add_mx_mx,tr[id].add_unmx_mx,tr[id].add_unmx_mx);
	}if(tr[rs].mx==mx){
		add_tag(rs,tr[id].add_mx,tr[id].add_mx_mx,tr[id].add_unmx,tr[id].add_unmx_mx);
	}else{
		add_tag(rs,tr[id].add_mx_mx,tr[id].add_mx_mx,tr[id].add_unmx_mx,tr[id].add_unmx_mx);
	}tr[id].add_mx=tr[id].add_mx_mx=tr[id].add_unmx=tr[id].add_unmx_mx=0;
}void build(int id,int l,int r){
	tr[id].l=l,tr[id].r=r,tr[id].len=r-l+1;
	if(l==r){
		tr[id].sum=tr[id].mx=tr[id].his_mx_mx=a[l];
		tr[id].mx_num=1,tr[id].sec=-1e18;
	}else{
		const int mid=l+r>>1;
		build(ls,l,mid);
		build(rs,mid+1,r);
		push_up(id);
	}
}void up_date_mn(int id,int l,int r,long long mn){
	if(tr[id].mx<=mn){
		return;
	}if(tr[id].l>=l&&tr[id].r<=r&&tr[id].sec<mn){
		tr[id].sum-=(tr[id].mx-mn)*tr[id].mx_num;
		tr[id].add_mx-=tr[id].mx-mn;
		tr[id].mx=mn;
	}else{
		push_down(id);
		int mid=tr[id].l+tr[id].r>>1;
		if(mid>=l){
			up_date_mn(ls,l,r,mn);
		}if(mid<r){
			up_date_mn(rs,l,r,mn);
		}push_up(id);
	}
}void up_date_add(int id,int l,int r,long long add){
	if(tr[id].l>=l&&tr[id].r<=r){
		tr[id].sum+=tr[id].len*add;
		tr[id].mx+=add;
		tr[id].his_mx_mx=max(tr[id].his_mx_mx,tr[id].mx);
		if(tr[id].sec!=-1e18){
			tr[id].sec+=add;
		}tr[id].add_mx+=add;
		tr[id].add_unmx+=add;
		tr[id].add_mx_mx=max(tr[id].add_mx_mx,tr[id].add_mx);
		tr[id].add_unmx_mx=max(tr[id].add_unmx_mx,tr[id].add_unmx);
	}else{
		push_down(id);
		const int mid=tr[id].l+tr[id].r>>1;
		if(mid>=l){
			up_date_add(ls,l,r,add);
		}if(mid<r){
			up_date_add(rs,l,r,add);
		}push_up(id);
	}
}long long query_sum(int id,int l,int r){
	if(tr[id].l>=l&&tr[id].r<=r){
		return tr[id].sum;
	}else{
		push_down(id);
		const int mid=tr[id].l+tr[id].r>>1;
		long long sum=0;
		if(mid>=l){
			sum+=query_sum(ls,l,r);
		}if(mid<r){
			sum+=query_sum(rs,l,r);
		}push_up(id);
		return sum;
	}
}long long query_mx(int id,int l,int r){
	if(tr[id].l>=l&&tr[id].r<=r){
		return tr[id].mx;
	}else{
		push_down(id);
		const int mid=tr[id].l+tr[id].r>>1;
		long long sum=-1e18;
		if(mid>=l){
			sum=max(sum,query_mx(ls,l,r));
		}if(mid<r){
			sum=max(sum,query_mx(rs,l,r));
		}push_up(id);
		return sum;
	}
}long long query_his(int id,int l,int r){
	if(tr[id].l>=l&&tr[id].r<=r){
		return tr[id].his_mx_mx;
	}else{
		push_down(id);
		const int mid=tr[id].l+tr[id].r>>1;
		long long sum=-1e18;
		if(mid>=l){
			sum=max(sum,query_his(ls,l,r));
		}if(mid<r){
			sum=max(sum,query_his(rs,l,r));
		}push_up(id);
		return sum;
	}
}void check(){
	for(int i=1;i<=n;i++){
		cout<<"sum"<<query_sum(1,i,i);
		cout<<"mx"<<query_mx(1,i,i);
		cout<<"his"<<query_his(1,i,i);
		cout<<endl;
	}
}signed main(){
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i]);
	}build(1,1,n);
	int op,l,r;
	long long val;
	while(q--){
		scanf("%d%d%d",&op,&l,&r);
		if(op==1){
			scanf("%lld",&val);
			up_date_add(1,l,r,val);
		}else if(op==2){
			scanf("%lld",&val);
			up_date_mn(1,l,r,val);
		}else if(op==3){
			printf("%lld\n",query_sum(1,l,r));
		}else if(op==4){
			printf("%lld\n",query_mx(1,l,r));
		}else if(op==5){
			printf("%lld\n",query_his(1,l,r));
		}//check();
	}return 0;
}/*
笔记：
lazytag关系复杂时还是要慢慢来
*/