当前位置： 首页 > article >正文

P6242 【模板】线段树 3（区间最值操作、区间历史最值）

article 2025/2/28 23:01:49

文章目录

  • 【模板】线段树 3（区间最值操作、区间历史最值）](https://www.luogu.com.cn/problem/P6242)

【模板】线段树 3（区间最值操作、区间历史最值）](https://www.luogu.com.cn/problem/P6242)

用线段树维护一个区间最大值、区间最小值

那个B数组不纯纯来捣乱的吗

那不得建两棵线段树

很显然，第一遍自己打的代码是没有仔细思考pushdown和pushup的

先记住现在过了的模板吧

这道题也是一道模板题，需要学一下思路，然后把板子记住

面向题解学习

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
#define ls (u<<1)
#define rs (u<<1|1)
#define mid ((l+r)>>1)
const int N=1e5+10;
ll a[N];

struct Tree
{
  ll add[N<<2];
  ll maxn[N<<2];
  ll minn[N<<2];
  ll sum[N<<2];
  
  Tree()
  {
    memset(add,0,sizeof add);
    memset(maxn,0,sizeof maxn);
    memset(minn,0,sizeof minn);
    memset(sum,0,sizeof sum);
  }
  
  void pushup(int u)
  {
      sum[u]=sum[rs]+sum[ls];
    	maxn[u]=max(maxn[ls],maxn[rs]);
    	minn[u]=min(minn[ls],minn[rs]);
  }
  
  void pushdown(int u,int l, int r)
  {
    	
  }
  
  void build(int u,int l, int r)
  {
    
    if(l==r)
    {
      maxn[u]=a[r];
      minn[u]=a[r];
      sum[u]=a[r];
      return ;
    }
    build(ls,l,mid);
    build(rs,mid+1,r);
  }
  
  void pushdown(int u,int l, int r)
  {
    if(add[u])
    {
      sum[ls]=(sum[ls]+(mid-l+1)*add[u]);
      sum[rs]=(sum[ls]+(r-mid)*add[u]);
      add[ls]+=add[u];
      add[rs]+=add[u];
    }
    add[u]=0;
  }
  
  
  void modify_add(int u, int l, int r, int L, int R,ll d)
  {
    if(L<=l&&r<=R)
    {
      add[u]+=d;
      return;
    }
    else
    {
      pushdown(u,l,r);
      if(L<=mid) modify_add(ls,l,mid,L,R,d);
      if(R>mid) modify_add(rs,mid+1,r,L,R,d);
      pushup(u);
    }
  }
  
  void modify_min(int u,int l,int r,int L, int R, ll k)
  {
    if(L<=l&&r<=R)
    {
      minn[u]=min(minn[u],k);
    }
    pushdown(u,l,r);
    if(L<=mid) modify_min(ls,l,mid,L,R,k);
    if(R>mid) modify_min(rs,mid+1,r,L,R,k);
    pushup(u);
  }
  
  ll query_max(int u,int l,int r,int L, int R)
  {
    if(L<=l&&r<=R)
    {
      return maxn[u];
    }
    pushdown(u,l,r);
    ll maxn=-(1<<30);
    
    if(L<=mid) maxn=max(maxn,query_max(ls,l,mid,L,R));
    if(R>mid) maxn=max(maxn,query_max(rs,mid+1,r,L,R));
    
    return maxn;
  }
  
  ll query_min(int u,int l,int r,int L, int R)
  {
    if(L<=l&&r<=R)
    {
      return maxn[u];
    }
    pushdown(u,l,r);
    ll minn=(1<<30);
    
    if(L<=mid) minn=min(minn,query_min(ls,l,mid,L,R));
    if(R>mid) minn=min(minn,query_min(rs,mid+1,r,L,R));
    
    return minn;
  }
  
  ll query_sum(int u,int l,int r,int L, int R)
  {
    if(L<=l&&r<=R)
    {
      return sum[u];
    }
    pushdown(u,l,r);
    ll ans=0;
    
    if(L<=mid) ans+=query_sum(ls,l,mid,L,R);
    if(R>mid) ans+=query_sum(rs,mid+1,r,L,R);
    
    return ans;
  }
  
}tr[2];



signed main()
{
  int n,m;
  cin>>n>>m;
  
  for(int i=1;i<=n;i++) cin>>a[i];
  
  tr[0].build(1,1,n);
  tr[1].build(1,1,n);
  
  while(m--)
  {
    int op;
    ll l,r,k,v;
    cin>>op>>l>>r;
    
    if(op==1)
    {
      
      cin>>k;
      tr[0].modify_add(1,l,r,1,n,k);
    }
    else if(op==2)
    {
      cin>>v;
      tr[0].modify_min(1,l,r,1,n,v);
    }
    else if(op==3)
    {
      cout<<tr[0].query_sum(1,l,r,1,n)<<endl;
    }
    else if(op==4)
    {
      cout<<tr[0].query_max(1,l,r,1,n)<<endl;
    }
    else
    {
      cout<<tr[1].query_max(1,l,r,1,n)<<endl;
    }
  }
  return 0;
}

学习5，6测试点思路

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
#define ls (u<<1)
#define rs (u<<1|1)
#define mid ((l+r)>>1)
const int N=1e5+10;
ll a[N];
ll l,r,k,v;

struct Tree
{
  ll maxa[N<<2];
  ll maxb[N<<2];
  ll minn[N<<2];
  ll sum[N<<2];
  ll tag1[N<<2];
  ll tag2[N<<2];
 
  Tree()
  {
    memset(maxa,0,sizeof maxa);
    memset(maxb,0,sizeof maxb);
    memset(minn,0,sizeof minn);
    memset(sum,0,sizeof sum);
    memset(tag1,0,sizeof tag1);
    memset(tag2,0,sizeof tag2);
  }
  
  void pushup(int u)
  {
      sum[u]=sum[rs]+sum[ls];
    	maxa[u]=max(maxa[ls],maxa[rs]);
    	//minn[u]=min(minn[ls],minn[rs]);
    	maxb[u]=max(maxb[ls],maxb[rs]);
  }
  
  void pushdown(int u,int l, int r)
  {
    	ll k1=tag1[u],k2=tag2[u];
    	if(k1&&k2)
    	{
    	    sum[ls]+=k1,sum[rs]+=k1;
        	maxb[ls]=max(maxb[ls],maxa[ls]+k2);
        	maxb[rs]=max(maxb[rs],maxa[rs]+k2);
        	maxa[ls]+=k1,maxa[rs]+=k1;
        	tag2[ls]=max(tag2[ls],tag1[ls]+k1);
        	tag2[rs]=max(tag2[rs],tag1[rs]+k1);
        	tag1[ls]+=k1,tag1[rs]+=k1;
        	tag1[u]=0,tag2[u]=0;
    	}
    	
  }
  
  void build(int u,int l, int r)
  {
    
    if(l==r)
    {
      maxa[u]=a[r];
      maxb[u]=a[r];
      minn[u]=a[r];
      sum[u]=a[r];
      return ;
    }
    build(ls,l,mid);
    build(rs,mid+1,r);
    pushup(u);
  }
  
  
  void modify_add(int u, int l, int r, int L, int R)
  {
    if(L<=l&&r<=R)
    {
      sum[u]+=(r-l+1)*k; 
      tag1[u]+=k;
      tag2[u]=max(tag1[u],tag2[u]);
      maxa[u]+=k;
      maxb[u]=max(maxb[u],maxa[u]);
      return;
    }
    else
    {
      pushdown(u,l,r);
      if(L<=mid) modify_add(ls,l,mid,L,R);
      if(R>mid) modify_add(rs,mid+1,r,L,R);
      pushup(u);
    }
  }
  
  //先不管这个
  void modify_min(int u,int l,int r,int L, int R)
  {
    if(L<=l&&r<=R)
    {
      minn[u]=min(minn[u],v);
    }
    pushdown(u,l,r);
    if(L<=mid) modify_min(ls,l,mid,L,R);
    if(R>mid) modify_min(rs,mid+1,r,L,R);
    pushup(u);
  }
  
  ll query_maxa(int u,int l,int r,int L, int R)
  {
    if(L<=l&&r<=R)
    {
      return maxa[u];
    }
    pushdown(u,l,r);
    ll maxn=-(1<<30);
    
    if(L<=mid) maxn=max(maxn,query_maxa(ls,l,mid,L,R));
    if(R>mid) maxn=max(maxn,query_maxa(rs,mid+1,r,L,R));
    
    return maxn;
  }
  
  ll query_maxb(int u,int l,int r,int L, int R)
  {
    if(L<=l&&r<=R)
    {
      return maxb[u];
    }
    pushdown(u,l,r);
    ll maxn=-(1<<30);
    
    if(L<=mid) maxn=max(maxn,query_maxb(ls,l,mid,L,R));
    if(R>mid) maxn=max(maxn,query_maxb(rs,mid+1,r,L,R));
    
    return maxn;
  }
  
  
  
  
  ll query_sum(int u,int l,int r,int L, int R)
  {
    if(L<=l&&r<=R)
    {
      return sum[u];
    }
    pushdown(u,l,r);
    ll ans=0;
    
    if(L<=mid) ans+=query_sum(ls,l,mid,L,R);
    if(R>mid) ans+=query_sum(rs,mid+1,r,L,R);
    
    return ans;
  }
  
}tr[1];



signed main()
{
  int n,m;
  cin>>n>>m;
  
  for(int i=1;i<=n;i++) cin>>a[i];
  
  tr[0].build(1,1,n);
  
  while(m--)
  {
    int op;
    
    cin>>op>>l>>r;
    
    if(op==1)
    {
      cin>>k;
      tr[0].modify_add(1,1,n,l,r);
    }
    else if(op==2)
    {
      cin>>v;
      //tr[0].modify_min(1,1,n,l,r);
    }
    else if(op==3)
    {
      cout<<tr[0].query_sum(1,1,n,l,r)<<endl;
    }
    else if(op==4)
    {
      cout<<tr[0].query_maxa(1,1,n,l,r)<<endl;
    }
    else
    {
      cout<<tr[0].query_maxb(1,1,n,l,r)<<endl;
    }
  }
  return 0;
}

过了1，5，6

#include<bits/stdc++.h>

using namespace std;
#define int long long 
typedef long long ll;
#define ls (u<<1)
#define rs (u<<1|1)
#define mid ((l+r)>>1)
const int N=1e5+10;
ll a[N];
ll l,r,k,v;

struct Tree
{
  ll maxa[N<<4];
  ll maxb[N<<4];
  ll minn[N<<4];
  ll sum[N<<4];
  ll tag1[N<<4];
  ll tag2[N<<4];
  ll tag3[N<<4];
  ll tag4[N<<4];
  ll se[N<<4];
  ll cnt[N<<4];
 
  Tree()
  {
    
  }
  
  void pushup(int u)
  {
      sum[u]=sum[rs]+sum[ls];
    	maxa[u]=max(maxa[ls],maxa[rs]);
    	//minn[u]=min(minn[ls],minn[rs]);
    	maxb[u]=max(maxb[ls],maxb[rs]);
    if(maxa[ls]==maxa[rs])
    {
      se[u]=max(se[ls],se[rs]);
      cnt[u]=cnt[ls]+cnt[rs];
    }
    else if(maxa[ls]>maxa[rs])
    {
      se[u]=max(se[ls],maxa[rs]);
      cnt[u]=cnt[ls];
    }
    else
    {
      se[u]=max(se[rs],maxa[ls]);
      cnt[u]=cnt[rs];
    }
  }
  
  void change(int k1,int k2,int k3,int k4,int u,int l,int r)
  {
      sum[u]+=cnt[u]*k1+k3*(ll)(r-l+1-cnt[u]);
      maxb[u]=max(maxb[u],maxa[u]+k2);
    	maxa[u]+=k1;
    	if(se[u]!=-2e9) se[u]+=k3;
    	tag2[u]=max(tag2[u],tag1[u]+k2);
    	tag4[u]=max(tag4[u],tag3[u]+k4);
    	tag1[u]+=k1;
    	tag3[u]+=k3;
  }
  
  void pushdown(int u,int l, int r)
  {
    	ll maxn=max(maxa[ls],maxa[rs]);
    	if(maxa[ls]==maxn)
        change(tag1[u],tag2[u],tag3[u],tag4[u],ls,l,mid);
    	else
        change(tag3[u],tag4[u],tag3[u],tag4[u],ls,l,mid);
    	
    	if(maxa[rs]==maxn)
        change(tag1[u],tag2[u],tag3[u],tag4[u],rs,mid+1,r);
    	else
        change(tag3[u],tag4[u],tag3[u],tag4[u],rs,mid+1,r);
        
      tag1[u]=tag2[u]=tag3[u]=tag4[u]=0;
    	
  }
  
  void build(int u,int l, int r)
  {
    
    if(l==r)
    {
      maxa[u]=a[r];
      maxb[u]=a[r];
      sum[u]=a[r];
      cnt[u]=1;
      se[u]=-2e9;
      return ;
    }
    build(ls,l,mid);
    build(rs,mid+1,r);
    pushup(u);
  }
  
  
  void modify_add(int u, int l, int r, int L, int R)
  {
    if(L<=l&&r<=R)
    {
      sum[u]+=cnt[u]*k+k*(ll)(r-l+1-cnt[u]);
      maxa[u]+=k;
      maxb[u]=max(maxb[u],maxa[u]);
      if(se[u]!=-2e9) se[u]+=k;
      
      tag1[u]+=k;
      tag2[u]=max(tag1[u],tag2[u]);
      
      tag3[u]+=k;
      tag4[u]=max(tag4[u],tag3[u]);
      
      return;
    }
    else
    {
      pushdown(u,l,r);
      if(L<=mid) modify_add(ls,l,mid,L,R);
      if(R>mid) modify_add(rs,mid+1,r,L,R);
      pushup(u);
    }
  }
  
  //先不管这个
  void modify_min(int u,int l,int r,int L, int R)
  {
    if(L<=l&&r<=R&&se[u]<v)
    {
      ll x=maxa[u]-v;
      sum[u]-=cnt[u]*x;
      maxa[u]=v,tag1[u]-=x;
      return;
    }
    pushdown(u,l,r);
    if(L<=mid) modify_min(ls,l,mid,L,R);
    if(R>mid) modify_min(rs,mid+1,r,L,R);
    pushup(u);
  }
  
  
  
  ll query_maxa(int u,int l,int r,int L, int R)
  {
    if(L<=l&&r<=R)
    {
      return maxa[u];
    }
    pushdown(u,l,r);
    ll maxn=-2e9;
    
    if(L<=mid) maxn=max(maxn,query_maxa(ls,l,mid,L,R));
    if(R>mid) maxn=max(maxn,query_maxa(rs,mid+1,r,L,R));
    
    return maxn;
  }
  
  ll query_maxb(int u,int l,int r,int L, int R)
  {
    if(L<=l&&r<=R)
    {
      return maxb[u];
    }
    pushdown(u,l,r);
    ll maxn=-2e9;
    
    if(L<=mid) maxn=max(maxn,query_maxb(ls,l,mid,L,R));
    if(R>mid) maxn=max(maxn,query_maxb(rs,mid+1,r,L,R));
    
    return maxn;
  }
  
  
  
  
  ll query_sum(int u,int l,int r,int L, int R)
  {
    if(L<=l&&r<=R)
    {
      return sum[u];
    }
    pushdown(u,l,r);
    ll ans=0;
    
    if(L<=mid) ans+=query_sum(ls,l,mid,L,R);
    if(R>mid) ans+=query_sum(rs,mid+1,r,L,R);
    
    return ans;
  }
  
}tr[1];



signed main()
{
  ll n,m;
  cin>>n>>m;
  
  for(int i=1;i<=n;i++) cin>>a[i];
  
  tr[0].build(1,1,n);
  
  while(m--)
  {
    int op;
    
    cin>>op>>l>>r;
    
    if(op==1)
    {
      cin>>k;
      tr[0].modify_add(1,1,n,l,r);
    }
    else if(op==2)
    {
      cin>>v;
      tr[0].modify_min(1,1,n,l,r);
    }
    else if(op==3)
    {
      cout<<tr[0].query_sum(1,1,n,l,r)<<endl;
    }
    else if(op==4)
    {
      cout<<tr[0].query_maxa(1,1,n,l,r)<<endl;
    }
    else
    {
      cout<<tr[0].query_maxb(1,1,n,l,r)<<endl;
    }
  }
  return 0;
}

尝试用题解代码写

#include<bits/stdc++.h>

using namespace std;
#define int long long 
typedef long long ll;
#define ls (u<<1)
#define rs (u<<1|1)
#define mid ((l+r)>>1)
const int N=1e5+10;
ll a[N];
ll l,r,k,v;

struct Tree
{
  ll maxa[N<<4];
  ll maxb[N<<4];
  ll minn[N<<4];
  ll sum[N<<4];
  ll tag1[N<<4];
  ll tag2[N<<4];
  ll tag3[N<<4];
  ll tag4[N<<4];
  ll se[N<<4];
  ll cnt[N<<4];
 
  Tree()
  {
    
  }
  
  void pushup(int u)
  {
      sum[u]=sum[rs]+sum[ls];
    	maxa[u]=max(maxa[ls],maxa[rs]);
    	//minn[u]=min(minn[ls],minn[rs]);
    	maxb[u]=max(maxb[ls],maxb[rs]);
    if(maxa[ls]==maxa[rs])
    {
      se[u]=max(se[ls],se[rs]);
      cnt[u]=cnt[ls]+cnt[rs];
    }
    else if(maxa[ls]>maxa[rs])
    {
      se[u]=max(se[ls],maxa[rs]);
      cnt[u]=cnt[ls];
    }
    else
    {
      se[u]=max(se[rs],maxa[ls]);
      cnt[u]=cnt[rs];
    }
  }
  
  void build(int u,int l, int r)
  {
    
    if(l==r)
    {
      maxa[u]=a[r];
      maxb[u]=a[r];
      sum[u]=a[r];
      cnt[u]=1;
      se[u]=-2e9;
      return ;
    }
    build(ls,l,mid);
    build(rs,mid+1,r);
    pushup(u);
  }
  
  
  void change(int k1,int k2,int k3,int k4,int u,int l,int r)
  {
      sum[u]+=cnt[u]*k1+k3*(ll)(r-l+1-cnt[u]);
      maxb[u]=max(maxb[u],maxa[u]+k2);
    	maxa[u]+=k1;
    	if(se[u]!=-2e9) se[u]+=k3;
    	tag2[u]=max(tag2[u],tag1[u]+k2);
    	tag4[u]=max(tag4[u],tag3[u]+k4);
    	tag1[u]+=k1;
    	tag3[u]+=k3;
  }
  
  void pushdown(int u,int l, int r)
  {
    	ll maxn=max(maxa[ls],maxa[rs]);
    	if(maxa[ls]==maxn)
        change(tag1[u],tag2[u],tag3[u],tag4[u],ls,l,mid);
    	else
        change(tag3[u],tag4[u],tag3[u],tag4[u],ls,l,mid);
    	
    	if(maxa[rs]==maxn)
        change(tag1[u],tag2[u],tag3[u],tag4[u],rs,mid+1,r);
    	else
        change(tag3[u],tag4[u],tag3[u],tag4[u],rs,mid+1,r);
        
      tag1[u]=tag2[u]=tag3[u]=tag4[u]=0;
    	
  }
  
  
  
  void modify_add(int u, int l, int r, int L, int R)
  {
    if(L>l||r>R) return;
    if(L<=l&&r<=R)
    {
      sum[u]+=cnt[u]*k+k*(ll)(r-l+1-cnt[u]);
      maxa[u]+=k;
      maxb[u]=max(maxb[u],maxa[u]);
      if(se[u]!=-2e9) se[u]+=k;
      
      tag1[u]+=k;
      tag2[u]=max(tag1[u],tag2[u]);
      
      tag3[u]+=k;
      tag4[u]=max(tag4[u],tag3[u]);
      
      return;
    }
    pushdown(u,l,r);
    modify_add(ls,l,mid,L,R);
    modify_add(rs,mid+1,r,L,R);
    pushup(u);
  }
  
  void modify_min(int u,int l,int r,int L, int R)
  {
    if(L>l||r>R||v>=maxa[u]) return; 
    if(L<=l&&r<=R&&se[u]<v)
    {
      ll x=maxa[u]-v;
      sum[u]-=cnt[u]*x;
      maxa[u]=v;
      tag1[u]-=x;
      return;
    }
    pushdown(u,l,r);
    modify_min(ls,l,mid,L,R);
    modify_min(rs,mid+1,r,L,R);
    pushup(u);
  }
 
  ll query_sum(int u,int l,int r,int L, int R)
  {
    if(L>l||r>R) return 0;
    if(L<=l&&r<=R)
    {
      return sum[u];
    }
    
    pushdown(u,l,r);
 
    return query_sum(ls,l,mid,L,R)+query_sum(rs,mid+1,r,L,R);
  }
  
  ll query_maxa(int u,int l,int r,int L, int R)
  {
    if(L>l||r>R) return -2e9;
    if(L<=l&&r<=R)
    {
      return maxa[u];
    }
    pushdown(u,l,r);
    
    return max(query_maxa(ls,l,mid,L,R),query_maxa(rs,mid+1,r,L,R));
  }
  
  ll query_maxb(int u,int l,int r,int L, int R)
  {
    if(L>l||r>R) return -2e9;
    if(L<=l&&r<=R)
    {
      return maxb[u];
    }
    pushdown(u,l,r);

    return max(query_maxa(ls,l,mid,L,R),query_maxa(rs,mid+1,r,L,R));
    
  }
  
}tr[1];



signed main()
{
  ll n,m;
  cin>>n>>m;
  
  for(int i=1;i<=n;i++) cin>>a[i];
  
  tr[0].build(1,1,n);
  
  while(m--)
  {
    int op;
    
    cin>>op>>l>>r;
    
    if(op==1)
    {
      cin>>k;
      tr[0].modify_add(1,1,n,l,r);
    }
    else if(op==2)
    {
      cin>>v;
      tr[0].modify_min(1,1,n,l,r);
    }
    else if(op==3)
    {
      cout<<tr[0].query_sum(1,1,n,l,r)<<endl;
    }
    else if(op==4)
    {
      cout<<tr[0].query_maxa(1,1,n,l,r)<<endl;
    }
    else
    {
      cout<<tr[0].query_maxb(1,1,n,l,r)<<endl;
    }
  }
  return 0;
}

ac代码

#include<bits/stdc++.h>

using namespace std;
#define int long long 
typedef long long ll;
#define ls (u<<1)
#define rs (u<<1|1)
#define mid ((l+r)>>1)
const int N=1e7+10;
ll a[N];
ll k,v;

struct Tree
{
  ll maxa[N<<4];
  ll maxb[N<<4];
  ll minn[N<<4];
  ll sum[N<<4];
  ll tag1[N<<4];
  ll tag2[N<<4];
  ll tag3[N<<4];
  ll tag4[N<<4];
  ll se[N<<4];
  ll cnt[N<<4];
 
  Tree()
  {
    //memset(maxa,0,sizeof maxa);
  }
  
  void pushup(int u)
  {
      sum[u]=sum[rs]+sum[ls];
    	maxa[u]=max(maxa[ls],maxa[rs]);
    	//minn[u]=min(minn[ls],minn[rs]);
    	maxb[u]=max(maxb[ls],maxb[rs]);
    if(maxa[ls]==maxa[rs])
    {
      se[u]=max(se[ls],se[rs]);
      cnt[u]=cnt[ls]+cnt[rs];
    }
    else if(maxa[ls]>maxa[rs])
    {
      se[u]=max(se[ls],maxa[rs]);
      cnt[u]=cnt[ls];
    }
    else
    {
      se[u]=max(se[rs],maxa[ls]);
      cnt[u]=cnt[rs];
    }
  }
  
  void build(int u,int l, int r)
  {
    
    if(l==r)
    {
      maxa[u]=a[r];
      maxb[u]=a[r];
      sum[u]=a[r];
      cnt[u]=1;
      se[u]=-2e9;
      return ;
    }
    build(ls,l,mid);
    build(rs,mid+1,r);
    pushup(u);
  }
  
  
  void change(int k1,int k2,int k3,int k4,int u,int l,int r)
  {
      sum[u]+=cnt[u]*k1+k3*(ll)(r-l+1-cnt[u]);
      maxb[u]=max(maxb[u],maxa[u]+k2);
    	maxa[u]+=k1;
    	if(se[u]!=-2e9) se[u]+=k3;
    	tag2[u]=max(tag2[u],tag1[u]+k2);
    	tag4[u]=max(tag4[u],tag3[u]+k4);
    	tag1[u]+=k1;
    	tag3[u]+=k3;
  }
  
  void pushdown(int u,int l, int r)
  {
    	ll maxn=max(maxa[ls],maxa[rs]);
    	if(maxa[ls]==maxn)
        change(tag1[u],tag2[u],tag3[u],tag4[u],ls,l,mid);
    	else
        change(tag3[u],tag4[u],tag3[u],tag4[u],ls,l,mid);
    	
    	if(maxa[rs]==maxn)
        change(tag1[u],tag2[u],tag3[u],tag4[u],rs,mid+1,r);
    	else
        change(tag3[u],tag4[u],tag3[u],tag4[u],rs,mid+1,r);
        
      tag1[u]=tag2[u]=tag3[u]=tag4[u]=0;
    	
  }
  
  
  
  void modify_add(int u, int l, int r, int L, int R)
  {
    if(L<=l&&r<=R)
    {
      sum[u]+=cnt[u]*k+k*(ll)(r-l+1-cnt[u]);
      maxa[u]+=k;
      maxb[u]=max(maxb[u],maxa[u]);
      if(se[u]!=-2e9) se[u]+=k;
      
      tag1[u]+=k;
      tag2[u]=max(tag1[u],tag2[u]);
      
      tag3[u]+=k;
      tag4[u]=max(tag4[u],tag3[u]);
      
      return;
    }
    else
    {
      pushdown(u,l,r);
      if(L<=mid) modify_add(ls,l,mid,L,R);
      if(R>mid) modify_add(rs,mid+1,r,L,R);
      pushup(u);
    }
  }
  
  void modify_min(int u,int l,int r,int L, int R)
  {
    // woc为什么？，为什么加上L>l||r>R就是wa一片
    if(maxa[u]<=v) return;
    if(L<=l&&r<=R&&se[u]<v)
    {
      ll x=maxa[u]-v;
      sum[u]-=cnt[u]*x;
      maxa[u]=v;
      tag1[u]-=x;
      return;
    }
    pushdown(u,l,r);
    
    if(L<=mid) modify_min(ls,l,mid,L,R);
    if(R>mid) modify_min(rs,mid+1,r,L,R);
    
    pushup(u);
  }
 
  ll query_sum(int u,int l,int r,int L, int R)
  {
    if(L<=l&&r<=R)
    {
      return sum[u];
    }
    pushdown(u,l,r);
    ll ans=0;
    
    if(L<=mid) ans+=query_sum(ls,l,mid,L,R);
    if(R>mid) ans+=query_sum(rs,mid+1,r,L,R);
    
    return ans;
  }
  
  ll query_maxa(int u,int l,int r,int L, int R)
  {
    if(L<=l&&r<=R)
    {
      return maxa[u];
    }
    pushdown(u,l,r);
    ll maxn=-2e9;
    
    if(L<=mid) maxn=max(maxn,query_maxa(ls,l,mid,L,R));
    if(R>mid) maxn=max(maxn,query_maxa(rs,mid+1,r,L,R));
    
    return maxn;
  }
  
  ll query_maxb(int u,int l,int r,int L, int R)
  {
    if(L<=l&&r<=R)
    {
      return maxb[u];
    }
    pushdown(u,l,r);
    ll maxn=-2e9;
    
    if(L<=mid) maxn=max(maxn,query_maxb(ls,l,mid,L,R));
    if(R>mid) maxn=max(maxn,query_maxb(rs,mid+1,r,L,R));
    
    return maxn;
  }
  
}tr[1];



signed main()
{
  ll n,m;
  cin>>n>>m;
  ll l,r;
  for(int i=1;i<=n;i++) cin>>a[i];
  
  tr[0].build(1,1,n);
  
  while(m--)
  {
    int op;
    
    cin>>op>>l>>r;
    
    if(op==1)
    {
      cin>>k;
      tr[0].modify_add(1,1,n,l,r);
    }
    else if(op==2)
    {
      cin>>v;
      tr[0].modify_min(1,1,n,l,r);
    }
    else if(op==3)
    {
      cout<<tr[0].query_sum(1,1,n,l,r)<<endl;
    }
    else if(op==4)
    {
      cout<<tr[0].query_maxa(1,1,n,l,r)<<endl;
    }
    else
    {
      cout<<tr[0].query_maxb(1,1,n,l,r)<<endl;
    }
  }
  return 0;
}

http://www.kler.cn/a/280856.html

相关文章：

  • 2024广东省职业技能大赛云计算赛项实战——安装ELK日志分析服务
  • 可定制化内容具体识别事物，多方位同时监管的智慧快消开源了
  • C++常见的十种常见排序算法汇总
  • WebRTC 实时通信：构建高效网页视频通话的秘诀
  • Java基础（4）- IDEA
  • 宝塔安装yasd 远程调试 swoole
  • 153页PPT丨麦肯锡-咨询公司流程管理体系规划建设方法论
  • 8.28（C++QT）C++绪论 数据类型--作业
  • 【Python】从基础到进阶（六）：深入理解Python中的面向对象编程（OOP）
  • Prometheus+exporter+Grafana
  • Apache Dubbo关键点分析
  • 经典算法之链表篇
  • clucene demo编译
  • 牛客NC313 两个数组的交集 C++
  • windows C++-Lambda表达式(三)
  • Spark MLlib 特征工程系列—特征转换Tokenizer和移除停用词
  • 2024.08.22 校招 实习 内推 面经
  • git安装及常用命令
  • CSS3【待总结学习】
  • C++编程语言——基础设施：类型和声明