链接
区间最值操作
HDU-5306
支持对区间取 \(\min\)，维护区间 \(\max\)，查询区间和。
很容易想到一个暴力，我们每一次找出这个区间的最大值 \(mx\)，如果 \(mx>x\)，那么暴力修改这个位置的值，否则已经修改完毕，退出，时间复杂度为 \(O(n^2 \log n)\)。
打一打补丁，对线段树上的每一个区间维护区间最大值 \(mx\)，这个区间中最大值出现的次数 \(t\)，区间次大值 \(se\)，当然还要维护区间和 \(sum\)。
现在考虑打上区间取 \(\min\) 标记
- 如果 \(mx\le x\)，那么对 \(sum\) 就没有修改。
- 如果 \(se<x<mx\)，那么 \(sum=sum-(mx-x)\times t\)。
- 如果 \(x\le se<mx\)，此时无法直接更新节点信息，故向下左右子树递归。我们分别 DFS 这个节点的两个孩子，如果当前 DFS 的过程中遇到了前两种情况，就直接修改打上标记然后退出，否则就继续 DFS。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define ls p<<1
#define rs p<<1|1
#define ll long long
inline char gc()
{
static char buf[1 << 20/*这里很玄学，改成其他数字可能更快*/], *p1 = buf, *p2 = buf;
return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20/*改成和上面一样的数字*/, stdin), p1 == p2) ? EOF : *p1 ++;
}
inline void read(int &n) // 用法 read(n);
{
bool w = 0;
char c = gc();
for(; c < 48 || c > 57; c = gc())
w = c == 45;
for(n = 0; c >= 48 && c <= 57; c = gc())
n = n * 10 + c - 48;
n = w ? -n : n;
}
const int N=1e6+7;
int T,n,m,a[N],mx[N<<2],se[N<<2],cnt[N<<2],tag[N<<2];
ll sum[N<<2];
inline void pushup(int p){
sum[p]=sum[ls]+sum[rs];
if(mx[ls]==mx[rs]){
mx[p]=mx[ls],se[p]=max(se[ls],se[rs]);
cnt[p]=cnt[ls]+cnt[rs];
}
else if(mx[ls]>mx[rs]){
mx[p]=mx[ls],se[p]=max(se[ls],mx[rs]);
cnt[p]=cnt[ls];
}
else{
mx[p]=mx[rs],se[p]=max(se[rs],mx[ls]);
cnt[p]=cnt[rs];
}
return;
}
inline void build(int p,int l,int r){
tag[p]=-1;
if(l==r){
sum[p]=mx[p]=a[l];
cnt[p]=1,se[p]=-1;
return;
}
int mid=(l+r)>>1;
build(ls,l,mid),build(rs,mid+1,r);
pushup(p);
return;
}
inline void pushtag(int p,int tg){
if(mx[p]<=tg)return;
sum[p]+=(ll)(tg-mx[p])*cnt[p];
mx[p]=tag[p]=tg;
return;
}
inline void pushdown(int p){
if(tag[p]==-1)return;
pushtag(ls,tag[p]),pushtag(rs,tag[p]);
tag[p]=-1;
return;
}
inline void update(int p,int l,int r,int s,int t,int val){
if(mx[p]<=val)return;
if(s<=l&&r<=t&&se[p]<val){
pushtag(p,val);
return;
}
int mid=(l+r)>>1;
pushdown(p);
if(s<=mid)update(ls,l,mid,s,t,val);
if(t>mid)update(rs,mid+1,r,s,t,val);
pushup(p);
return;
}
inline int querymax(int p,int l,int r,int s,int t){
if(s<=l&&r<=t)return mx[p];
int mid=(l+r)>>1,res=-1;
pushdown(p);
if(s<=mid)res=max(res,querymax(ls,l,mid,s,t));
if(t>mid)res=max(res,querymax(rs,mid+1,r,s,t));
return res;
}
inline ll querysum(int p,int l,int r,int s,int t){
if(s<=l&&r<=t)return sum[p];
int mid=(l+r)>>1;ll res=0;
pushdown(p);
if(s<=mid)res+=querysum(ls,l,mid,s,t);
if(t>mid)res+=querysum(rs,mid+1,r,s,t);
return res;
}
inline void solve(){
read(n); read(m);
for(int i=1;i<=n;i++)read(a[i]);
build(1,1,n);
for(int i=1;i<=m;i++){
int op,l,r,val;
read(op); read(l); read(r);
if(!op){
read(val);
update(1,1,n,l,r,val);
}
else if(op==1)printf("%d\n",querymax(1,1,n,l,r));
else printf("%lld\n",querysum(1,1,n,l,r));
}
return;
}
int main(){
scanf("%d",&T);
while(T--)solve();
return 0;
}