Gorgeous Sequence(区间更新取min)

题：http://acm.hdu.edu.cn/showproblem.php?pid=5306

题意：给定n个数的序列，操作一：对于[x,y]取min（ai，t），操作二：取[x,y]最大值，操作三：取[x,y]的ai和

分析：华点：增设一个次大值，不直接，更新传递下去，完成更新。

1. 设fir为区间最大值，sec为区间次大值，cnt为区间fir个数，sum为区间和
2. 当区间最大值tr[root].fir<=t时，可不用操作
3. 当区间最大值tr[root].fir>t且区间次大值<=t时，更新sum=sum-cnt*（fir-t），fir=t；

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define lson root<<1,l,midd
#define rson root<<1|1,midd+1,r
#define pb push_back
typedef long long ll;
const int M=1000005;
struct node{
    int fir,sec,cnt;
    ll sum;
    node(int a=0,int b=0,int c=-1,ll d=0):fir(a),sec(b),cnt(c),sum(d){}
}tr[M<<2];
int a[M];
void Push_Up(int root){
    int ls=root<<1,rs=ls+1;
    tr[root].sum=tr[ls].sum+tr[rs].sum;
    if(tr[ls].fir==tr[rs].fir){
        tr[root].fir=tr[ls].fir;
        tr[root].sec=max(tr[ls].sec,tr[rs].sec);
        tr[root].cnt=tr[ls].cnt+tr[rs].cnt;
    }
    else{
        if(tr[ls].fir<tr[rs].fir)
            swap(ls,rs);
        tr[root].fir=tr[ls].fir;
        tr[root].sec=max(tr[ls].sec,tr[rs].fir);
        tr[root].cnt=tr[ls].cnt;
    }
}
void Dec(int root,int maxx){
    if(tr[root].fir<=maxx)
        return;
    tr[root].sum-=(ll)tr[root].cnt*(tr[root].fir-maxx);
    tr[root].fir=maxx;
}
void Pushdown(int root){
    Dec(root<<1,tr[root].fir);
    Dec(root<<1|1,tr[root].fir);
}
void Modify(int L,int R,int w,int root,int l,int r){
    if(L<=l&&r<=R){
        if(tr[root].fir<=w)///整个区间无需更新
            return;
        if(tr[root].sec<w){///更新掉最大值
            Dec(root,w);
            return;
        }
        ///否则不返回，继续往下更新（点睛之处）
    }
    Pushdown(root);
    int midd=(l+r)>>1;
    if(L<=midd)
        Modify(L,R,w,lson);
    if(R>midd)
        Modify(L,R,w,rson);
    Push_Up(root);
}

void build(int root,int l,int r){
    if(l==r){
        tr[root]=node(a[l],-1,1,a[l]);
        return ;
    }
    int midd=(l+r)>>1;
    build(lson);
    build(rson);
    Push_Up(root);
}
int QueryMax(int L,int R,int root,int l,int r){
    if(L<=l&&r<=R){
        return tr[root].fir;
    }
    Pushdown(root);
    int res=0;
    int midd=(l+r)>>1;
    if(L<=midd)
        res=max(res,QueryMax(L,R,lson));
    if(R>midd)
        res=max(res,QueryMax(L,R,rson));
    return res;
}
ll QuerySum(int L,int R,int root,int l,int r){
    if(L<=l&&r<=R)
        return tr[root].sum;
    Pushdown(root);
    int midd=(l+r)>>1;
    ll res=0;
    if(L<=midd)
        res+=QuerySum(L,R,lson);
    if(R>midd)
        res+=QuerySum(L,R,rson);
    return res;
}
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        int n,m;
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)
            scanf("%lld",&a[i]);
        build(1,1,n);
        for(int op,x,y,w,i=1;i<=m;i++){
            scanf("%d%d%d",&op,&x,&y);
            if(op==0){
                scanf("%d",&w);
                Modify(x,y,w,1,1,n);
            }
            else if(op==1){
                printf("%d
",QueryMax(x,y,1,1,n));
            }
            else
                printf("%lld
",QuerySum(x,y,1,1,n));
        }
    }
    return 0;
}