题目链接

<h1>题目描述</h1>

（本人喜欢用 Vjudge 所以就放那里的链接啦。
给定一个序列，要求实现区间求最大值，区间求和，区间对一个数取min。

<h1>解题报告</h1>

开始挖十一集训的坟了......
这一题是吉司机线段树模板题的简化版本。
大家都会维护最大值和和，怎么实现那个取min的操作呢？
我们考虑对于每个区间都先维护出这个区间的最大值 max，次大值 se，最大值出现的次数 cnt。
这样在覆盖的时候分类讨论一下，设这个区间要对x整体取min：
如果当前区间 $max \leq x$ 就不用继续处理了因为这个区间不会改变；
如果当前区间 $ max \geq x $ 并且 $se \leq x $ 那么只需要将这个区间的最大值改一下就可以了。
否则就递归左右子树继续找，最后合并一下就可以了。
合并也是要分类讨论的 $qwq$.
合并注意下要判断两边的max相等的情况，这时候的cnt和se取值都与一般情况不同。
还有一个小问题：我不知道为什么我如果去掉注释里的CLR函数（即memset） 就会提示我MLE？我十分的疑惑，如果有知道的神犇请在评论里告诉我 $qwq$ 谢谢。
另外这个题目还有一个 进阶版本，按照这种分类讨论操作的思想写就可以了，只不过可能代码量会 略 长一些。

<h1>代码实现</h1>

#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>

#define Re register
#define LL long long
#define CLR(a,b) memset(a,b,sizeof(a))
#define FOR(i,a,b) for(Re int i = a;i <= b;++i)
#define ROF(i,a,b) for(Re int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 1000000+5;

struct SegmentTree New(int ,int ,SegmentTree ,SegmentTree *);

struct SegmentTree{
    int l,r,max,se,cnt;
    LL sum;
    SegmentTree lc,rc;
    
    static SegmentTree *build(int l,int r){
        int mid = (l + r) >> 1;
        return l == r ? New(l,r,NULL,NULL) : New(l,r,build(l,mid),build(mid+1,r));
    }
    
    void pushup(){
        if(lc->max > rc->max){
            max = lc->max;
            se = std::max(lc->se,rc->max);
            cnt = lc->cnt;
        }
        if(lc->max == rc->max){
            max = lc->max;
            se = std::max(lc->se,rc->se);
            cnt = lc->cnt + rc->cnt;
        }
        if(lc->max < rc->max){
            max = rc->max;
            se = std::max(lc->max,rc->se);
            cnt = rc->cnt;
        }
        sum = lc->sum + rc->sum;
    }
    
    void cover(int delta){
        if(max <= delta) return;
        sum += 1llcnt(delta-max);
        max = delta;
    }
    
    void pushdown(){
        lc->cover(max);
        rc->cover(max);
    }
    
    void update(int pos,int x){
        if(l == r){
            max = sum = x;
            se = -1;cnt = 1;
            return;
        }
        int mid = (l + r) >> 1;
        if(pos <= mid) lc->update(pos,x);
        else rc->update(pos,x);
        pushup();
    }
    
    void modify(int L,int R,int x){
        if(x >= max) return;
        if(L == l && R == r && x > se){
            cover(x);
            return;
        }
        pushdown();
        int mid = (l + r) >> 1;
        if(R <= mid) lc->modify(L,R,x);
        else if(L > mid) rc->modify(L,R,x);
        else lc->modify(L,mid,x),rc->modify(mid+1,R,x);
        pushup();
    }
    
    int qmax(int L,int R){
        if(L == l && R == r) return max;
        pushdown();
        int mid = (l + r) >> 1;
        if(R <= mid) return lc->qmax(L,R);
        if(L > mid) return rc->qmax(L,R);
        return std::max(lc->qmax(L,mid),rc->qmax(mid+1,R));
    }
    
    LL qsum(int L,int R){
        if(L == l && R == r) return sum;
        pushdown();
        int mid = (l + r) >> 1;
        if(R <= mid) return lc->qsum(L,R);
        if(L > mid) return rc->qsum(L,R);
        return lc->qsum(L,mid) + rc->qsum(mid+1,R);
    }
}pool[MAXN<<2],frog = pool,segt;

SegmentTree New(int l,int r,SegmentTree lc,SegmentTree *rc){
    SegmentTree *ret = ++frog;
    ret->l = l;ret->r = r;ret->lc = lc;ret->rc = rc;
    ret->max = ret->se = -1;ret->cnt = ret->sum = 0;
    return ret;
}

inline void Solve(){
    frog = pool;//CLR(pool,0);
    int N,M;scanf("%d%d",&N,&M);
    segt = SegmentTree::build(1,N);
    FOR(i,1,N){
        int x;scanf("%d",&x);
        segt->update(i,x);
    }
    while(M--){
        int opt,l,r;
        scanf("%d%d%d",&opt,&l,&r);
        if(opt == 0){
            int t;scanf("%d",&t);
            segt->modify(l,r,t);
        }
        if(opt == 1){
            printf("%dn",segt->qmax(l,r));
        }
        if(opt == 2){
            printf("%lldn",segt->qsum(l,r));
        }
    }
}

int main(){
    int T;scanf("%d",&T);
    while(T--) Solve();
    return 0;
}