http://acm.hdu.edu.cn/showproblem.php?pid=5306
给一个数组，m次操作：
1:l r x，将a[i](l<=i<=r)=min(a[i],x)
2:l r，求区间最大值。
3:l r，求区间和。
吉司机线段树，论文题，论文讲的很详细了。
维护一个最大值mx和次大值se，分类讨论：
当mx<=x显然没有影响。
当se<x<mx打标记修改区间。
否则暴力递归两个儿子。
通过奇（看）技（论）淫（文）巧能够证明复杂度是O(mlogn)。
（但是我跑得贼慢……）
#include<map>
#include<cmath>
#include<stack>
#include<queue>
#include<cstdio>
#include<cctype>
#include<vector>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=1e6+;
inline int read(){
int X=,w=;char ch=;
while(!isdigit(ch)){w|=ch=='-';ch=getchar();}
while(isdigit(ch))X=(X<<)+(X<<)+(ch^),ch=getchar();
return w?-X:X;
}
ll sum[N*];
int n,m,b[N],mx[N*],se[N*],lz[N*],cnt[N*];
inline void upt(int a){
int ls=a<<,rs=a<<|;
if(mx[ls]==mx[rs]){
mx[a]=mx[ls];se[a]=max(se[ls],se[rs]);
cnt[a]=cnt[ls]+cnt[rs];
}
else if(mx[ls]<mx[rs]){
mx[a]=mx[rs];se[a]=max(mx[ls],se[rs]);
cnt[a]=cnt[rs];
}else{
mx[a]=mx[ls];se[a]=max(mx[rs],se[ls]);
cnt[a]=cnt[ls];
}
sum[a]=sum[ls]+sum[rs];
}
void build(int a,int l,int r){
lz[a]=-;
if(l==r){
sum[a]=mx[a]=b[l];
se[a]=-;cnt[a]=;
return;
}
int mid=(l+r)>>;
build(a<<,l,mid);build(a<<|,mid+,r);
upt(a);
}
inline void push(int a){
if(lz[a]==-)return;
int ls=a<<,rs=a<<|;
if(mx[ls]>lz[a]){
sum[ls]-=(ll)cnt[ls]*(mx[ls]-lz[a]);
mx[ls]=lz[a];
lz[ls]=lz[a];
}
if(mx[rs]>lz[a]){
sum[rs]-=(ll)cnt[rs]*(mx[rs]-lz[a]);
mx[rs]=lz[a];
lz[rs]=lz[a];
}
lz[a]=-;
}
void mdy(int a,int l,int r,int l1,int r1,int x){
if(r<l1||r1<l||mx[a]<=x)return;
if(l1<=l&&r<=r1&&se[a]<x){
sum[a]-=(ll)cnt[a]*(mx[a]-x);
mx[a]=x;lz[a]=x;
return;
}
int mid=(l+r)>>;
push(a);
mdy(a<<,l,mid,l1,r1,x);mdy(a<<|,mid+,r,l1,r1,x);
upt(a);
}
ll qry_sum(int a,int l,int r,int l1,int r1){
if(r<l1||r1<l)return ;
if(l1<=l&&r<=r1)return sum[a];
int mid=(l+r)>>;
push(a);
return qry_sum(a<<,l,mid,l1,r1)+qry_sum(a<<|,mid+,r,l1,r1);
}
int qry_mx(int a,int l,int r,int l1,int r1){
if(r<l1||r1<l)return ;
if(l1<=l&&r<=r1)return mx[a];
int mid=(l+r)>>;
push(a);
return max(qry_mx(a<<,l,mid,l1,r1),qry_mx(a<<|,mid+,r,l1,r1));
}
int main(){
int t=read();
while(t--){
n=read(),m=read();
for(int i=;i<=n;i++)b[i]=read();
build(,,n);
while(m--){
int op=read(),x=read(),y=read();
if(op==)mdy(,,n,x,y,read());
if(op==)printf("%d\n",qry_mx(,,n,x,y));
if(op==)printf("%lld\n",qry_sum(,,n,x,y));
}
}
return ;
}
+++++++++++++++++++++++++++++++++++++++++++
+本文作者：luyouqi233。 +
+欢迎访问我的博客：http://www.cnblogs.com/luyouqi233/+
+++++++++++++++++++++++++++++++++++++++++++