现在有这样的一个问题：
你有一个长度为\(n(n\le1e6)\)的序列，你将会进行\(m(m\le1e6)\)次操作，每次操作属于下列三种形式之一：
- \(0\ l\ r\ x\)，表示对于每一个\(i(l\le i\le r)\)，进行\(a_i = min(a_i,x)\)操作。
- \(1\ l\ r\)，询问区间\([l,r]\)内当前的区间最大值
- \(2\ l\ r\)，询问区间\([l,r]\)内的区间和，即\(\sum_{i=l}^ra_i\)
对于这样的问题（包括其各种加强版），\(jls\)在\(2016\)的国家集训队论文集中给出了如下的解法，即\(segment\ tree\ beats\)，一种采用势能思想的线段树。
思路：
考虑线段树的每个节点维护下列的信息：区间最大值，区间严格次大值(没有标记为\(-1/-INF\))，区间最大值的出现次数，区间和。
我们每次进行操作\(0\)，即修改操作，分下列三种情况讨论修改：
\(1.\)如果\(x >= ma[rt]\)，很明显，不用修改直接返回即可。
\(2.\)如果\(se[rt] < x < ma[rt]\)，用\(x\)和\(ma[rt]\)的差值再加上我们维护的\(cnt[rt]\)来更新\(sum[rt]\)即可，再把\(ma[rt]\)更新为\(x\)。
\(3.\)如果\(x <= se[rt]\)，那么就暴力的向左右儿子递归更新，因为我们会把叶子的\(se[rt]\)初始化为一个题目中不涉及的负数，所以到叶子节点后一定会更新并回溯。
再考虑\(pushup\)函数的维护操作，这个部分只需要讨论左右儿子的最大值的大小关系，然后利用其次大值和最大值来更新当前节点对应的值即可。
考虑\(pushdown\)函数，在本题中，我们可以直接使用\(ma\)数组来代替懒惰标记，因为下推时，我们对于当前节点是否需要更新，只需要考虑其和其父节点的最值大小关系即可，如果当前节点最值比父节点的最值严格大于，那么就代表当前的节点需要被更新了，否则就不用更新。
关于时间复杂度：
\(jls\)在给出的论文中说是\(mlogn\)的，但是后面的博客中提到这个复杂度证明在涉及到同时具有区间加减等操作时，证明假了，但最坏也是不会超过\(nlog^2n\)，且大多数据下接近\(nlogn\)，所有可能是一种\(O(\)跑得过\()\)的复杂度(bushi........
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define eb emplace_back
#define MP make_pair
#define pii pair<int,int>
#define pll pair<ll,ll>
#define lson rt<<1
#define rson rt<<1|1
#define CLOSE std::ios::sync_with_stdio(false)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef double db;
const int INF = 0x3f3f3f3f;
const db eps = 1e-6;
const int N = 1e6 + 10;
struct node {
ll ma,se,cnt,sum;//ma区间最大值 se区间严格次大值 cnt区间最大值的个数
}tr[N<<2];
int n,m;ll a[N];
void pushup(int rt) {//维护次大值时情况多一点
tr[rt].sum = tr[lson].sum + tr[rson].sum;
tr[rt].ma = max(tr[lson].ma,tr[rson].ma);
if(tr[lson].ma == tr[rson].ma) {
tr[rt].cnt = tr[lson].cnt + tr[rson].cnt;
tr[rt].se = max(tr[lson].se,tr[rson].se);
}
else if(tr[lson].ma > tr[rson].ma) {
tr[rt].cnt = tr[lson].cnt;
tr[rt].se = max(tr[lson].se,tr[rson].ma);
}
else {
tr[rt].cnt = tr[rson].cnt;
tr[rt].se = max(tr[rson].se,tr[lson].ma);
}
}
void pushdown(int rt) {//最大值标记就相当于延迟标记 只有子节点的最大值比父节点的最大值大的时候才代表这个子节点该被更新了
if(tr[lson].ma > tr[rt].ma) {
tr[lson].sum -= (tr[lson].ma - tr[rt].ma) * tr[lson].cnt;
tr[lson].ma = tr[rt].ma;
}
if(tr[rson].ma > tr[rt].ma) {
tr[rson].sum -= (tr[rson].ma - tr[rt].ma) * tr[rson].cnt;
tr[rson].ma = tr[rt].ma;
}
}
void build(int rt,int l,int r) {
if(l == r) {
tr[rt] = {a[l],-1,1,a[l]}; return ;
}
tr[rt].ma = tr[rt].cnt = tr[rt].sum = 0;
tr[rt].se = -1;
int mid = (l + r) >> 1;
build(lson,l,mid); build(rson,mid+1,r);
pushup(rt);
}
//修改里面看似没有x<=tr[rt].se的操作但是 直到递归到叶子节点，叶子节点自身肯定是没有次大值的，所以就用pushup去更新父节点的se了
void modify(int rt,int l,int r,int L,int R,ll v) {
if(v >= tr[rt].ma) return ;
if(l >= L && r <= R && v > tr[rt].se) {//修改的v都是正数 所以到modify到叶子节点一定会做出更新操作
tr[rt].sum -= (tr[rt].ma - v) * tr[rt].cnt;
tr[rt].ma = v;
return ;
}
pushdown(rt);
int mid = (l + r) >> 1;
if(L <= mid) modify(lson,l,mid,L,R,v);
if(R > mid) modify(rson,mid+1,r,L,R,v);
pushup(rt);
}
ll qma(int rt,int l,int r,int L,int R) {
if(l >= L && r <= R) return tr[rt].ma;
int mid = (l + r) >> 1; ll ans = 0;
pushdown(rt);
if(L <= mid) ans = max(ans,qma(lson,l,mid,L,R));
if(R > mid) ans = max(ans,qma(rson,mid+1,r,L,R));
return ans;
}
ll qsum(int rt,int l,int r,int L,int R) {
if(l >= L && r <= R) return tr[rt].sum;
int mid = (l + r) >> 1; ll ans = 0;
pushdown(rt);
if(L <= mid) ans += qsum(lson,l,mid,L,R);
if(R > mid) ans += qsum(rson,mid+1,r,L,R);
return ans;
}
void solve() {
scanf("%d%d",&n,&m);
for(int i = 1;i <= n;i ++) {
scanf("%lld",&a[i]);
}
build(1,1,n);
int op,l,r;ll x;
while(m--) {
scanf("%d",&op);
if(op == 0) {
scanf("%d%d%lld",&l,&r,&x);
modify(1,1,n,l,r,x);
// cout << "--------\n";
}
else if(op == 1) {
scanf("%d%d",&l,&r);
ll res = qma(1,1,n,l,r);
printf("%lld\n",res);
// cout << "--------\n";
}
else if(op == 2) {
scanf("%d%d",&l,&r);
ll res = qsum(1,1,n,l,r);
printf("%lld\n",res);
// cout << "--------\n";
}
}
}
int main() {
int T;scanf("%d",&T);
while(T--) solve();
return 0;
}