给定一个数组a，实现三种操作：
1.将[l,r]区间的数修改为min（a _ i,t）
2.求[l,r]区间最大值
3.求[l,r]区间和

之前der了几个细节问题，下次左右子节点一定在函数开头算出lchild和rchild。
解法不难理解，使用线段树维护区间和、区间最大值、区间最大值的个数和区间次大值。当要修改的数（t）大于等于区间最大值的时候，直接返回。大于区间次大值但小于区间最大值，我们可以利用已经维护的区间最大值个数去更新区间和，并下放懒标记。否则继递归。
可以证明时间复杂度是O(mlog^2 n)，证明过程详见吉老师当年在国家集训队的论文。
代码如下：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n, m;
ll a[1000005];
struct treenode{
    ll cha;
    ll sum,max,maxcount,secmax;
    #define sum(x) tree[x].sum
    #define cha(x) tree[x].cha
    #define segmax(x) tree[x].max
    #define maxc(x) tree[x].maxcount//统计区间内最大值的个数
    #define secm(x) tree[x].secmax//区间次大值
}tree[1000005<<2];
void pushup(ll p){
    sum(p)=sum(p<<1)+sum(p<<1|1);
    if(segmax(p<<1)==segmax(p<<1|1)){
        secm(p)=max(secm(p<<1),secm(p<<1|1));
        segmax(p)=segmax(p<<1);
        maxc(p)=maxc(p<<1)+maxc(p<<1|1);
    }
    else if(segmax(p<<1)<segmax(p<<1|1)){
        secm(p)=max(segmax(p<<1),secm(p<<1|1));
        segmax(p)=segmax(p<<1|1);
        maxc(p)=maxc(p<<1|1);
    }
    else{
        secm(p)=max(segmax(p<<1|1),secm(p<<1));
        segmax(p)=segmax(p<<1);
        maxc(p)=maxc(p<<1);
    }
}
void pushdown(ll p){
    if(cha(p)!=-1)
    {
        ll lc=p<<1;
        ll rc=p<<1|1;
        if(cha(p)<segmax(lc)&&cha(p)>secm(lc)){
            sum(lc)-=1ll*(segmax(lc)-cha(p))*maxc(lc);
            cha(lc)=cha(p);
            segmax(lc)=cha(p);

        }
        if(cha(p)<segmax(rc)&&cha(p)>secm(rc)){
            sum(rc)-=1ll*(segmax(rc)-cha(p))*maxc(rc);
            cha(rc)=cha(p);
            segmax(rc)=cha(p);
        }
        cha(p)=-1;
    }
}
void build(ll s, ll t, ll p) {
    //[s,t]区间建树，节点编号为p
    cha(p)=-1;
    if (s == t) {
        secm(p)=-1;
        maxc(p)=1;
        sum(p) = a[s];
        segmax(p) = a[s];
        return;
    }
    ll mid = s + t >>1;
    build(s, mid, p<<1);
    build(mid + 1, t, p <<1| 1);
    pushup(p);
}
ll getsum(ll l, ll r, ll s, ll t, ll p) {
    // [l,r] 为查询区间,[s,t] 为当前节点包含的区间,p 为当前节点的编号
    if (l <= s && t <= r)
        return sum(p);
    ll mid = s + t >>1, sum = 0;
    pushdown(p);
    if (l <= mid) sum += getsum(l, r, s, mid, p <<1);
    if (r > mid) sum += getsum(l, r, mid + 1, t, p <<1|1);
    return sum;
}
ll getmax(ll l, ll r, ll s, ll t, ll p) {
    // [l,r] 为查询区间,[s,t] 为当前节点包含的区间,p 为当前节点的编号
    if (l <= s && t <= r)
        return segmax(p);
    ll mid = (s + t) >>1, sum = 0;
    pushdown(p);
    if (l <= mid) sum = max(sum,getmax(l, r, s, mid, p <<1));
    if (r > mid) sum = max(sum,getmax(l, r, mid + 1, t, p <<1| 1));
    return sum;
}
//updateto为区间修改为某个值
void updateto(ll l, ll r, ll c, ll s, ll t, ll p) {
    if(c>=segmax(p))return;
    if (l <= s && t <= r&&c>secm(p)) {
            sum(p)-=1ll*(segmax(p)-c)*maxc(p);
            segmax(p)=c;
            cha(p)=c;
            return;
    }
    int mid = (s + t) >> 1;
    pushdown(p);
    if (l <= mid) updateto(l, r, c, s, mid, p<<1);
    if (r > mid) updateto(l, r, c, mid + 1, t, p<<1|1 );
    pushup(p);
}
int main() {
    int _;
    scanf("%d",&_);
    while(_--) {
        ll aa, l, r,t;
        scanf("%lld%lld",&m,&n);
        for (int i = 1; i <= m; i++) {
            scanf("%lld",&a[i]);
        }
        build(1, m, 1);
        while (n--) {
            scanf("%lld%lld%lld",&aa,&l,&r);
            if (aa == 0) {
                scanf("%lld",&t);
                updateto(l, r, t, 1, m, 1);
            } else if (aa == 1) {
                printf("%lld\n",getmax(l, r, 1, m, 1) );
            } else {
                printf("%lld\n",getsum(l, r, 1, m, 1) );
            }
        }
    }

}