Segment tree Beats
Segment tree Beats，吉司机线段树，主要是关于如何用线段树实现区间取min/max。我们先看一道例题：
HDU5306 Gorgeous Sequence
题目大意：给一个序列，要求支持区间取min（即对于一段区间，用min(a[i],x)替换a[i]（x已给出）），询问区间和以及区间最大值。
看到区间求和，区间最大，我们自然想到用线段树来解决这个问题，但我们如何解决区间区间取min？
既然用的是线段树，我们不妨试着打一下标记。我们维护一下区间最大值mx，区间严格次大值sx，区间最大值出现的次数cx，然后我们就可以分类讨论一下了：
1、x>=mx，明显对区间无影响，退出；
2、sx<x<=mx,此时mx会被更改成x，其它值则不变，对区间和sum的贡献为：(mx-x)*cx；
3、x<=sx,以此类推，显然我们不能继续这样推下去，但是我们可以跳到当前节点的两个子节点去处理这种情况，再pushup回来就搞定了。
另外，我们发现mx本身就可以作为取min标记，所以我们无需另外打标记。
时间复杂度：据说是O(nlog2n)?我太菜了，不会证。
放上代码：
#include<bits/stdc++.h>
using namespace std;
#define N 500010
#define LL long long
int T,n,m,a[N];
#define lc (p<<1)
#define rc (p<<1|1)
struct tree{
int l,r,mx,sx,cx;
LL sum;
}t[N<<];
void up(int p){
t[p].cx=;
t[p].sum=t[lc].sum+t[rc].sum;
t[p].mx=max(t[lc].mx,t[rc].mx);
t[p].sx=max(t[lc].sx,t[rc].sx);
if(t[lc].mx^t[rc].mx) t[p].sx=max(t[p].sx,min(t[lc].mx,t[rc].mx));
if(t[lc].mx==t[p].mx) t[p].cx+=t[lc].cx;
if(t[rc].mx==t[p].mx) t[p].cx+=t[rc].cx;
}
void build(int p,int l,int r){
t[p].l=l;t[p].r=r;
if(l==r){t[p].sum=t[p].mx=a[l];t[p].sx=-;t[p].cx=;return;}
int mid=(l+r)>>;
build(lc,l,mid);build(rc,mid+,r);up(p);
}
void MIN(int p,int v){
if(v>=t[p].mx) return;
t[p].sum+=1ll*(v-t[p].mx)*t[p].cx;t[p].mx=v;
}
void down(int p){MIN(lc,t[p].mx);MIN(rc,t[p].mx);}
void Min(int p,int l,int r,int v){
if(v>=t[p].mx) return;
if(l<=t[p].l&&t[p].r<=r&&t[p].sx<v){MIN(p,v);return;}
int mid=(t[p].l+t[p].r)>>;down(p);
if(l<=mid) Min(lc,l,r,v);
if(r> mid) Min(rc,l,r,v);
up(p);
}
LL query(int p,int l,int r,int op){
if(l<=t[p].l&&t[p].r<=r){
if(op==) return t[p].sum;
return t[p].mx;
}
int mid=(t[p].l+t[p].r)>>;down(p);LL ans;
if(op==){
ans=;
if(l<=mid) ans+=query(lc,l,r,op);
if(r> mid) ans+=query(rc,l,r,op);
}
else{
ans=-;
if(l<=mid) ans=max(ans,query(lc,l,r,op));
if(r> mid) ans=max(ans,query(rc,l,r,op));
}
up(p);return ans;
}
//segment tree
int main(){
int op,x,y,z;
scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++) scanf("%d",&a[i]);
build(,,n);
for(int i=;i<=m;i++){
scanf("%d%d%d",&op,&x,&y);
if(!op){scanf("%d",&z);Min(,x,y,z);}
else{printf("%lld\n",query(,x,y,op));}
}
}
return ;
}
再看一道例题：
WOJ#3706 BZOJ 4695 最假女选手
Description
在刚刚结束的水题嘉年华的压轴节目放水大赛中，wyywyy如愿以偿的得到了最假女选手的奖项。但是作为主办人的C_SUNSHINE为了证明wyywyy确实在放水，决定出一道基础题考察wyywyy的姿势水平。给定一个长度为 N序列，编号从1 到 N。要求支持下面几种操作：
1.给一个区间[L,R] 加上一个数x
2.把一个区间[L,R] 里小于x 的数变成x
3.把一个区间[L,R] 里大于x 的数变成x
4.求区间[L,R] 的和
5.求区间[L,R] 的最大值
6.求区间[L,R] 的最小值
Input
第一行一个整数 N表示序列长度。
第二行N 个整数Ai 表示初始序列。
第三行一个整数M 表示操作个数。
接下来M 行，每行三或四个整数，第一个整数Tp 表示操作类型，接下来L,R,X 或L,R 表述操作数。
1<=tp<=6,N,M<=5*10^5,|Ai|<=10^8
Tp=1时,|x|<=1000
Tp=2或3时，|x|<=10^8
Output
对于每个4,5,6类型的操作输出一行一个整数表示答案。
Sample Input
2
1 2
2
2 1 2 2
4 1 2
Sample Output
4
解法：跟上一道题基本差不多，只是还要支持区间加，所以在下传标记时想清楚标记下传的顺序就ok了。
放上我奇慢无比的代码：
#include<bits/stdc++.h>
using namespace std;
#define N 500010
#define LL long long
#define INF 1<<30
int n,m,a[N];
#define lc (p<<1)
#define rc (p<<1|1)
struct node{
int l,r,len,mx,mn,sx,sn,cx,cn;
LL laz,sum;
}t[N<<];
void up(int p){
t[p].cx=t[p].cn=;
t[p].sum=t[lc].sum+t[rc].sum;
t[p].mx=max(t[lc].mx,t[rc].mx);
t[p].sx=max(t[lc].sx,t[rc].sx);
if(t[lc].mx^t[rc].mx) t[p].sx=max(t[p].sx,min(t[lc].mx,t[rc].mx));
if(t[p].mx==t[lc].mx) t[p].cx+=t[lc].cx;
if(t[p].mx==t[rc].mx) t[p].cx+=t[rc].cx;
t[p].mn=min(t[lc].mn,t[rc].mn);
t[p].sn=min(t[lc].sn,t[rc].sn);
if(t[lc].mn^t[rc].mn) t[p].sn=min(t[p].sn,max(t[lc].mn,t[rc].mn));
if(t[p].mn==t[lc].mn) t[p].cn+=t[lc].cn;
if(t[p].mn==t[rc].mn) t[p].cn+=t[rc].cn;
}
void build(int p,int l,int r){
t[p].l=l;t[p].r=r;t[p].len=r-l+;
if(l==r){
t[p].mx=t[p].mn=t[p].sum=a[l];t[p].cx=t[p].cn=;
t[p].sx=-INF;t[p].sn=INF;
return;
}
int mid=(l+r)>>;
build(lc,l,mid);build(rc,mid+,r);up(p);
}
void now(int p,int v){
t[p].sum+=1ll*t[p].len*v;t[p].laz+=v;
t[p].mx+=v;t[p].mn+=v;
if(t[p].sx!=-INF) t[p].sx+=v;
if(t[p].sn!= INF) t[p].sn+=v;
}
void MAX(int p,int v){
t[p].sum+=1ll*(v-t[p].mn)*t[p].cn;t[p].mn=v;
t[p].mx=max(v,t[p].mx);
if(t[p].mx==t[p].mn){
t[p].sum=1ll*t[p].len*v;t[p].cn=t[p].cx=t[p].len;t[p].sx=-INF;t[p].sn=INF;
}
else t[p].sx=max(v,t[p].sx);
}
void MIN(int p,int v){
t[p].sum+=1ll*(v-t[p].mx)*t[p].cx;t[p].mx=v;
t[p].mn=min(v,t[p].mn);
if(t[p].mx==t[p].mn){
t[p].sum=1ll*t[p].len*v;t[p].cn=t[p].cx=t[p].len;t[p].sx=-INF;t[p].sn=INF;
}
else t[p].sn=min(v,t[p].sn);
}
void down(int p){
if(t[p].laz){now(lc,t[p].laz);now(rc,t[p].laz);t[p].laz=;}
if(t[lc].mn<t[p].mn&&t[p].mn<t[lc].sn) MAX(lc,t[p].mn);
if(t[rc].mn<t[p].mn&&t[p].mn<t[rc].sn) MAX(rc,t[p].mn);
if(t[lc].sx<t[p].mx&&t[p].mx<t[lc].mx) MIN(lc,t[p].mx);
if(t[rc].sx<t[p].mx&&t[p].mx<t[rc].mx) MIN(rc,t[p].mx);
}
void add(int p,int l,int r,int v){
if(!v) return;
if(l<=t[p].l&&t[p].r<=r){now(p,v);return;}
int mid=(t[p].l+t[p].r)>>;down(p);
if(l<=mid) add(lc,l,r,v);
if(r> mid) add(rc,l,r,v);
up(p);
}
void Max(int p,int l,int r,int v){
if(t[p].mn>=v) return;
if(l<=t[p].l&&t[p].r<=r&&v<t[p].sn){MAX(p,v);return;}
int mid=(t[p].l+t[p].r)>>;down(p);
if(l<=mid) Max(lc,l,r,v);
if(r> mid) Max(rc,l,r,v);
up(p);
}
void Min(int p,int l,int r,int v){
if(t[p].mx<=v) return;
if(l<=t[p].l&&t[p].r<=r&&v>t[p].sx){MIN(p,v);return;}
int mid=(t[p].l+t[p].r)>>;down(p);
if(l<=mid) Min(lc,l,r,v);
if(r> mid) Min(rc,l,r,v);
up(p);
}
LL query(int p,int l,int r,int op){
if(l<=t[p].l&&t[p].r<=r){
if(op==) return t[p].sum;
if(op==) return t[p].mx;
if(op==) return t[p].mn;
}
int mid=(t[p].l+t[p].r)>>;LL ans;down(p);
if(op==){
ans=;
if(l<=mid) ans+=query(lc,l,r,op);
if(r> mid) ans+=query(rc,l,r,op);
}
if(op==){
ans=-INF;
if(l<=mid) ans=max(ans,query(lc,l,r,op));
if(r> mid) ans=max(ans,query(rc,l,r,op));
}
if(op==){
ans=INF;
if(l<=mid) ans=min(ans,query(lc,l,r,op));
if(r> mid) ans=min(ans,query(rc,l,r,op));
}
up(p);return ans;
}
//segment tree
int main(){
int op,x,y,z;
scanf("%d",&n);
for(int i=;i<=n;i++) scanf("%d",&a[i]);
scanf("%d",&m);build(,,n);
for(int i=;i<=m;i++){
scanf("%d%d%d",&op,&x,&y);
if(op<=){
scanf("%d",&z);
if(op==) add(,x,y,z);
if(op==) Max(,x,y,z);
if(op==) Min(,x,y,z);
}
else{printf("%lld\n",query(,x,y,op));}
}
return ;
}