求调

马蜂不咋好qwq

#include<bits/stdc++.h>
#define maxn 1000100
#define ll long long

using namespace std;

ll a[maxn],n,k;

struct node{
	ll l,r,sum,b,min;
}t[maxn<<2];

void push_up(ll p){
	t[p].sum=t[p<<1].sum+t[p<<1|1].sum;
}

void build(ll l,ll r,ll p){
	t[p].l=l;t[p].r=r;
	if(l==r){t[p].sum=a[l];return;}
	ll mid=l+r>>1;
	build(l,mid,p<<1);
	build(mid+1,r,p<<1|1);
	push_up(p);
}

void push_down(ll l,ll r,ll p){
	t[p<<1].b+=t[p].b;t[p<<1|1].b+=t[p].b;
	ll mid=l+r>>1;
	t[p<<1].sum+=t[p].b*(mid-l+1);
	t[p<<1|1].sum+=t[p].b*(r-mid);
	t[p].b=0;
}

void modify(ll lq,ll rq,ll l,ll r,ll x,ll p){
	if(l>=lq&&r<=rq){
		t[p].sum+=x*(r-l+1);
		t[p].b+=x;
		return ;
	}
	push_down(l,r,p);
	ll mid=l+r>>1;
	if(lq<=mid)modify(lq,rq,l,mid,x,p<<1);
	if(rq>mid)modify(lq,rq,mid+1,r,x,p<<1|1);
	push_up(p);
}

void dl(ll lq,ll rq,ll l ,ll r,ll x,ll p){
	if(l==r){
		t[p].sum=x;
		return ;
	}
	ll mid=l+r>>1;
	push_down(l,r,p);
	if(lq<=mid)dl(lq,rq,l,mid,x,p<<1);
	if(rq>mid)dl(lq,rq,mid+1,r,x,p<<1|1);
	push_up(p);
}

ll getsum(ll lq,ll rq,ll l,ll r,ll p){
	if(l>=lq&&r<=rq)return t[p].sum;
	ll mid=l+r>>1,ans=0;
	push_down(l,r,p);
	if(lq<=mid)ans+=getsum(lq,rq,l,mid,p<<1);
	if(rq>mid)ans+=getsum(lq,rq,mid+1,r,p<<1|1);
	return ans;
}

ll getmax(ll lq,ll rq,ll l,ll r,ll p){
	if(l==r)return t[p].sum;
	ll mid=l+r>>1,ans=-114514114514;
	push_down(l,r,p);
	if(lq<=mid)ans=max(getmax(lq,rq,l,mid,p<<1),ans);
	if(rq>mid)ans=max(getmax(lq,rq,mid+1,r,p<<1|1),ans);
	return ans;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>n;cin>>k;
	for(int i=1;i<=n;i++)cin>>a[i];
	build(1,n,1);
	
	while(k--){
		int opt,x,y,q;
		cin>>opt;
		if(opt==2){
			cin>>x>>y>>q;
			modify(x,y,1,n,q,1);
		}
		else if(opt==1){
			cin>>x>>y>>q;
			dl(x,y,1,n,q,1);
		}
			else{
			cin>>x>>y;
			cout<<getmax(x,y,1,n,1)<<"\n";
		}
	}
	return 0;
}

https://www.luogu.com.cn/record/172302682