P6242 【模板】线段树 3
支持区间加，区间取 \(\min\)，区间求和，区间 \(\max\)，区间历史 \(\max\)。
先提一嘴吉司机。
就是对线段树的每个节点记录最大值，严格次大值和最大值个数，只在 \(se<v<mx\) 的区间操作，否则向下递归。如果没有区间加，复杂度势能分析是 \(O((n+m)\log n)\) 的，否则为 \(O(m\log^2 n)\)。
考虑 \(\operatorname{pushdown}\) 需要的 \(\mathrm{tag}\)。
-
\(\mathrm{tag1}\)：区间 \(\max\) 的懒标记。
-
\(\mathrm{tag2}\)：区间非 \(\max\) 的懒标记。
-
\(\mathrm{tag3}\)：区间 \(\max\) 的懒标记的最大值。
-
\(\mathrm{tag4}\)：区间非 \(\max\) 的懒标记的最大值。
注意要先更新历史值再更新当前值。
点击查看代码
#include<bits/stdc++.h>
#define ll long long
#define N 500010
#define inf 2e9
using namespace std;
int read(){
int x=0,w=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
return x*w;
}
#define sum(x) tr[x].sum
#define len(x) tr[x].len
#define ma(x) tr[x].ma
#define cnt(x) tr[x].cnt
#define se(x) tr[x].se
#define mb(x) tr[x].mb
#define add1(x) tr[x].add1
#define add2(x) tr[x].add2
#define add3(x) tr[x].add3
#define add4(x) tr[x].add4
struct Tree{
ll sum;int len;
int ma,cnt,se,mb;
int add1,add2,add3,add4;
}tr[N<<2];
#define ls p<<1
#define rs p<<1|1
void pushup(int p){
sum(p)=sum(ls)+sum(rs);
ma(p)=max(ma(ls),ma(rs)),mb(p)=max(mb(ls),mb(rs));
if(ma(ls)==ma(rs))
se(p)=max(se(ls),se(rs)),cnt(p)=cnt(ls)+cnt(rs);
else if(ma(ls)>ma(rs))
se(p)=max(se(ls),ma(rs)),cnt(p)=cnt(ls);
else
se(p)=max(ma(ls),se(rs)),cnt(p)=cnt(rs);
}
void change(int p,int k1,int k2,int k3,int k4){
sum(p)+=1ll*k1*cnt(p)+1ll*k2*(len(p)-cnt(p));
mb(p)=max(mb(p),ma(p)+k3),ma(p)+=k1;
if(se(p)!=-inf)se(p)+=k2;
add3(p)=max(add3(p),add1(p)+k3);
add4(p)=max(add4(p),add2(p)+k4);
add1(p)+=k1,add2(p)+=k2;
}
void pushdown(int p){
int mx=max(ma(ls),ma(rs));
if(ma(ls)==mx)
change(ls,add1(p),add2(p),add3(p),add4(p));
else change(ls,add2(p),add2(p),add4(p),add4(p));
if(ma(rs)==mx)
change(rs,add1(p),add2(p),add3(p),add4(p));
else change(rs,add2(p),add2(p),add4(p),add4(p));
add1(p)=add2(p)=add3(p)=add4(p)=0;
}
void build(int p,int l,int r){
len(p)=r-l+1;
if(l==r){
sum(p)=ma(p)=mb(p)=read();
cnt(p)=1,se(p)=-inf;
return;
}
int mid=(l+r)>>1;
build(ls,l,mid),build(rs,mid+1,r);
pushup(p);
}
ll qsum(int p,int l,int r,int L,int R){
if(L<=l&&r<=R)return sum(p);
int mid=(l+r)>>1;pushdown(p);
ll ret=0;
if(L<=mid)ret+=qsum(ls,l,mid,L,R);
if(R>mid)ret+=qsum(rs,mid+1,r,L,R);
return ret;
}
int qma(int p,int l,int r,int L,int R){
if(L<=l&&r<=R)return ma(p);
int mid=(l+r)>>1;pushdown(p);
if(R<=mid)return qma(ls,l,mid,L,R);
if(L>mid)return qma(rs,mid+1,r,L,R);
return max(qma(ls,l,mid,L,R),qma(rs,mid+1,r,L,R));
}
int qmb(int p,int l,int r,int L,int R){
if(L<=l&&r<=R)return mb(p);
int mid=(l+r)>>1;pushdown(p);
if(R<=mid)return qmb(ls,l,mid,L,R);
if(L>mid)return qmb(rs,mid+1,r,L,R);
return max(qmb(ls,l,mid,L,R),qmb(rs,mid+1,r,L,R));
}
void uadd(int p,int l,int r,int L,int R,int k){
if(L<=l&&r<=R){
sum(p)+=1ll*k*len(p);
ma(p)+=k,mb(p)=max(mb(p),ma(p));
if(se(p)!=-inf)se(p)+=k;
add1(p)+=k,add2(p)+=k;
add3(p)=max(add3(p),add1(p)),add4(p)=max(add4(p),add2(p));
return;
}
int mid=(l+r)>>1;pushdown(p);
if(L<=mid)uadd(ls,l,mid,L,R,k);
if(R>mid)uadd(rs,mid+1,r,L,R,k);
pushup(p);
}
void umin(int p,int l,int r,int L,int R,int v){
if(L>r||R<l||v>=ma(p))return;
if(L<=l&&r<=R&&se(p)<v){
int k=ma(p)-v;
sum(p)-=1ll*cnt(p)*k;
ma(p)=v,add1(p)-=k;
return;
}
int mid=(l+r)>>1;pushdown(p);
umin(ls,l,mid,L,R,v);
umin(rs,mid+1,r,L,R,v);
pushup(p);
}
int n,m;
int main(){
n=read(),m=read();
build(1,1,n);
for(int opt,l,r;m;m--){
opt=read(),l=read(),r=read();
if(opt==1)uadd(1,1,n,l,r,read());
if(opt==2)umin(1,1,n,l,r,read());
if(opt==3)printf("%lld\n",qsum(1,1,n,l,r));
if(opt==4)printf("%d\n",qma(1,1,n,l,r));
if(opt==5)printf("%d\n",qmb(1,1,n,l,r));
}
return 0;
}