| 1234567 |
- #include <algorithm>
- #include <iostream>
- #include <limits>
- #include <vector>
- using namespace std;
- struct Node{long long sum=0,mx=0,se=-1;int cnt=0;};
- int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int T;cin>>T;while(T--){int n,q;cin>>n>>q;vector<long long>a(n);for(auto&x:a)cin>>x;vector<Node>tr(4*n);auto pull=[&](int u){auto&A=tr[u*2];auto&B=tr[u*2+1];tr[u].sum=A.sum+B.sum;if(A.mx==B.mx){tr[u].mx=A.mx;tr[u].cnt=A.cnt+B.cnt;tr[u].se=max(A.se,B.se);}else if(A.mx>B.mx){tr[u].mx=A.mx;tr[u].cnt=A.cnt;tr[u].se=max(A.se,B.mx);}else{tr[u].mx=B.mx;tr[u].cnt=B.cnt;tr[u].se=max(A.mx,B.se);}};auto build=[&](auto&&self,int u,int l,int r)->void{if(l==r){tr[u]={a[l],a[l],-1,1};return;}int m=(l+r)/2;self(self,u*2,l,m);self(self,u*2+1,m+1,r);pull(u);};auto apply=[&](int u,long long x){tr[u].sum-=(tr[u].mx-x)*tr[u].cnt;tr[u].mx=x;};auto push=[&](int u){if(tr[u*2].mx>tr[u].mx)apply(u*2,tr[u].mx);if(tr[u*2+1].mx>tr[u].mx)apply(u*2+1,tr[u].mx);};auto chmin=[&](auto&&self,int u,int l,int r,int ql,int qr,long long x)->void{if(qr<l||r<ql||tr[u].mx<=x)return;if(ql<=l&&r<=qr&&tr[u].se<x){apply(u,x);return;}push(u);int m=(l+r)/2;self(self,u*2,l,m,ql,qr,x);self(self,u*2+1,m+1,r,ql,qr,x);pull(u);};auto sum=[&](auto&&self,int u,int l,int r,int ql,int qr)->long long{if(ql<=l&&r<=qr)return tr[u].sum;push(u);int m=(l+r)/2;long long s=0;if(ql<=m)s+=self(self,u*2,l,m,ql,qr);if(qr>m)s+=self(self,u*2+1,m+1,r,ql,qr);return s;};auto mx=[&](auto&&self,int u,int l,int r,int ql,int qr)->long long{if(ql<=l&&r<=qr)return tr[u].mx;push(u);int m=(l+r)/2;long long z=0;if(ql<=m)z=max(z,self(self,u*2,l,m,ql,qr));if(qr>m)z=max(z,self(self,u*2+1,m+1,r,ql,qr));return z;};build(build,1,0,n-1);while(q--){int op,l,r;cin>>op>>l>>r;--l;--r;if(op==0){long long x;cin>>x;chmin(chmin,1,0,n-1,l,r,x);}else if(op==1)cout<<mx(mx,1,0,n-1,l,r)<<'\n';else cout<<sum(sum,1,0,n-1,l,r)<<'\n';}}}
|
