HDU5306 Gorgeous Sequence

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

题意：

三种操作
0 l r t: 使这个区间的每个值变成min(t,a[i])。 
1 l r: 输出区间最大值 
2 l r: 输出区间和
(1 <= n,m <= 1e6, 0 <= ai,t <= 2^31)

思路：
吉司机线段树模板题。
学知识点看论文比较好
具体实现读了这篇。https://www.cnblogs.com/MashiroSky/p/6642226.html
大致思想是：结点除了保存要求的元素和、最大值之外，再保存最大值、严格次大值、最大值个数，递归划分区间。复杂度貌似每次操作是接近 $O (l o g n)$ ,最差 $O (l o g n l o g n)$

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=1000000+1000;

int T,n,m,a[maxn];
int op,x,y,t;
struct Node{
    int ma,t,se;
    ll s;
    bool tag;
}tr[maxn*4];

int readint()
{
    char c=getchar();
    while(!isdigit(c))c=getchar();
    int x=0;
    while(isdigit(c))x=x*10+c-'0',c=getchar();
    return x;
}

void pushup(int o,int l,int r)
{
    int lc=o*2,rc=o*2+1,mid=(l+r)/2;
    if(tr[lc].ma==tr[rc].ma){
        tr[o].ma=tr[lc].ma;
        tr[o].t=tr[lc].t+tr[rc].t;
        tr[o].se=max(tr[lc].se,tr[rc].se);
    }else if(tr[lc].ma>tr[rc].ma){
        tr[o].ma=tr[lc].ma;
        tr[o].t=tr[lc].t;
        tr[o].se=max(tr[lc].se,tr[rc].ma);
    }else{
        tr[o].ma=tr[rc].ma;
        tr[o].t=tr[rc].t;
        tr[o].se=max(tr[lc].ma,tr[rc].se);
    }
    tr[o].s=tr[lc].s+tr[rc].s;
}

void build(int o,int l,int r)
{
    if(l==r){
        tr[o].tag=0;
        tr[o].ma=tr[o].s=a[l];
        tr[o].t=1;
        tr[o].se=-1;
    }else{
        int lc=o*2,rc=o*2+1,mid=(l+r)/2;
        build(lc,l,mid);
        build(rc,mid+1,r);
        pushup(o,l,r);
    }
}

void pushdown(int o)
{
    int lc=o*2,rc=o*2+1;
    int val=tr[o].ma;
    tr[o].tag=0;
    if(tr[lc].ma>val&&tr[lc].se<val){
        tr[lc].tag=1;
        tr[lc].s-=(tr[lc].ma-val)*(ll)tr[lc].t;
        tr[lc].ma=val;
    }
    if(tr[rc].ma>val&&tr[rc].se<val){
        tr[rc].tag=1;
        tr[rc].s-=(tr[rc].ma-val)*(ll)tr[rc].t;
        tr[rc].ma=val;
    }
}

void update(int o,int l,int r,int ql,int qr,int val)
{
    int lc=o*2,rc=o*2+1,mid=(l+r)/2;
    if(l==ql&&r==qr&&val>tr[o].se){
        if(val>=tr[o].ma)return;
        else{
            tr[o].s-=(tr[o].ma-val)*(ll)tr[o].t;
            tr[o].ma=val;
            tr[o].tag=1;
            return;
        }
    }
    if(tr[o].tag)pushdown(o);
    if(qr<=mid)update(lc,l,mid,ql,qr,val);
    else if(ql>mid)update(rc,mid+1,r,ql,qr,val);
    else update(lc,l,mid,ql,mid,val),update(rc,mid+1,r,mid+1,qr,val);
    pushup(o,l,r);
}

int querymax(int o,int l,int r,int ql,int qr)
{
    int lc=o*2,rc=o*2+1,mid=(l+r)/2;
    if(l==ql&&r==qr)return tr[o].ma;
    if(tr[o].tag)pushdown(o);
    if(qr<=mid)return querymax(lc,l,mid,ql,qr);
    else if(ql>mid)return querymax(rc,mid+1,r,ql,qr);
    else return max(querymax(lc,l,mid,ql,mid),querymax(rc,mid+1,r,mid+1,qr));
}

ll querysum(int o,int l,int r,int ql,int qr)
{
    int lc=o*2,rc=o*2+1,mid=(l+r)/2;
    if(l==ql&&r==qr)return tr[o].s;
    if(tr[o].tag)pushdown(o);
    if(qr<=mid)return querysum(lc,l,mid,ql,qr);
    else if(ql>mid)return querysum(rc,mid+1,r,ql,qr);
    else return querysum(lc,l,mid,ql,mid)+querysum(rc,mid+1,r,mid+1,qr);
}

int main()
{
    //freopen("input.in","r",stdin);
    T=readint();
    while(T--)
    {
        n=readint();m=readint();  
        for(int i=1;i<=n;i++)a[i]=readint();
        build(1,1,n);
        while(m--)
        {
            op=readint();x=readint();y=readint();
            if(op==0)t=readint(),update(1,1,n,x,y,t);
            else if(op==1)printf("%d\n",querymax(1,1,n,x,y));
            else printf("%lld\n",querysum(1,1,n,x,y));
        }
    }
    return 0;
}