这个题目是Segment-Tree-beats的论文的第一题。
首先我们考虑下这个问题的不同之处在于，有一个区间对x取max的操作。
那么如何维护这个操作呢？
就是对于线段树的区间，维护一个最大值标记，最大值出现次数，以及严格次大值。
接下来考虑处理操作。
首先如果x>maxv[o]证明已经是无所谓的，所以应该直接放弃。
如果v处于semx[o]<x<maxv[o]，证明只有最大值需要被修改。
其他的情况就继续向下递进就可以了。
那么我们证明一下为什么这么做复杂度是对的。
首先，如同论文中所说的，对于每个maxv可以看作是一个标记，把相同的maxv合并到第一个点，
可以发现semx的含义就是子树中最大的maxv。（因为最大值已经被缩到了这个点上）
每次暴力进入这些节点的时候，实际上就是将标记进行合并。
（也就是文章中所说的标记回收的理论）
这个题的难点就是为什么我这么暴力的回收依然可以是一个log的。
在每一次操作后会产生一类新的标记。
那么每次标记回收实际上就是有一类标记的权值-=1
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N=1e6+;
int a[N],n,m;
struct Segment_Tree{
#define lson (o<<1)
#define rson (o<<1|1)
int maxv[N<<],cntv[N<<],semx[N<<];
ll sumv[N<<];
inline void pushup(int o){
sumv[o]=sumv[lson]+sumv[rson];
maxv[o]=max(maxv[lson],maxv[rson]);
semx[o]=max(semx[lson],semx[rson]);cntv[o]=;
if(maxv[lson]!=maxv[rson])semx[o]=max(semx[o],min(maxv[lson],maxv[rson]));
if(maxv[o]==maxv[lson])cntv[o]+=cntv[lson];
if(maxv[o]==maxv[rson])cntv[o]+=cntv[rson];
}
inline void puttag(int o,int v){
if(v>=maxv[o])return;
sumv[o]+=1LL*(v-maxv[o])*cntv[o];maxv[o]=v;
}
inline void pushdown(int o){puttag(lson,maxv[o]);puttag(rson,maxv[o]);}
inline void build(int o,int l,int r){
if(l==r){
sumv[o]=maxv[o]=a[l];cntv[o]=;semx[o]=-;
return;
}
int mid=(l+r)>>;
build(lson,l,mid);build(rson,mid+,r);
pushup(o);
}
inline void optmax(int o,int l,int r,int ql,int qr,int v){
if(v>=maxv[o])return;
if(ql<=l&&r<=qr&&v>semx[o]){puttag(o,v);return;}
int mid=(l+r)>>;pushdown(o);
if(ql<=mid)optmax(lson,l,mid,ql,qr,v);
if(qr>mid)optmax(rson,mid+,r,ql,qr,v);
pushup(o);
}
inline ll querysum(int o,int l,int r,int ql,int qr){
if(ql<=l&&r<=qr)return sumv[o];
int mid=(l+r)>>;pushdown(o);ll ans=;
if(ql<=mid)ans+=querysum(lson,l,mid,ql,qr);
if(qr>mid)ans+=querysum(rson,mid+,r,ql,qr);
return ans;
}
inline int querymax(int o,int l,int r,int ql,int qr){
if(ql<=l&&r<=qr)return maxv[o];
pushdown(o);int mid=(l+r)>>,ans=-;
if(ql<=mid)ans=max(ans,querymax(lson,l,mid,ql,qr));
if(qr>mid)ans=max(ans,querymax(rson,mid+,r,ql,qr));
return ans;
}
}sgt;
inline int read(){
int f=,x=;char ch;
do{ch=getchar();if(ch=='-')f=-;}while(ch<''||ch>'');
do{x=x*+ch-'';ch=getchar();}while(ch>=''&&ch<='');
return f*x;
}
int main(){
int T=read();
while(T--){
n=read();m=read();
for(int i=;i<=n;i++)a[i]=read();
sgt.build(,,n);
while(m--){
int opt=read(),l=read(),r=read();
if(opt==){
int v=read();
sgt.optmax(,,n,l,r,v);
}
if(opt==)printf("%d\n",sgt.querymax(,,n,l,r));
if(opt==)printf("%lld\n",sgt.querysum(,,n,l,r));
}
}
}