_nothingGG @ 2024-12-07 17:09:44
#include<bits/stdc++.h>
namespace extX{
template<typename T>class SGT{
private:
struct node{
int lpoint,rpoint;
bool setting=false;
T add,mul,set,sum,max,min;
};
std::vector<node>v;
void Cover(int p){
if(v[p].setting){
// std::cout<<"!!!!\n";
v[p*2].setting=v[p*2+1].setting=true;
v[p*2].set=v[p*2+1].set=v[p].set;
v[p*2].add=v[p*2+1].add=0;
v[p*2].mul=v[p*2+1].mul=1;
v[p*2].sum=(v[p*2].rpoint-v[p*2].lpoint+1)*v[p].set;
v[p*2+1].sum=(v[p*2+1].rpoint-v[p*2+1].lpoint+1)*v[p].set;
v[p*2].max=v[p*2+1].max=v[p].set;
v[p*2].min=v[p*2+1].min=v[p].set;
}
}
void SumMul(int p){
if(!v[p].setting){
v[p*2].sum=v[p].mul*v[p*2].sum+(v[p*2].rpoint-v[p*2].lpoint+1)*v[p].add;
v[p*2+1].sum=v[p].mul*v[p*2+1].sum+v[p].add*(v[p*2+1].rpoint-v[p*2+1].lpoint+1);
v[p*2].max=v[p].mul*v[p*2].max+v[p].add;
v[p*2+1].max=v[p].mul*v[p*2+1].max+v[p].add;
v[p*2].min=v[p].mul*v[p*2].min+v[p].add;
v[p*2+1].min=v[p].mul*v[p*2+1].min+v[p].add;
v[p*2].mul*=v[p].mul;
v[p*2+1].mul*=v[p].mul;
v[p*2].add=v[p*2].add*v[p].mul+v[p].add;
v[p*2+1].add=v[p*2+1].add*v[p].mul+v[p].add;
v[p].mul=1;v[p].add=0;
}
}
void Transport(int p){Cover(p);SumMul(p);v[p].setting=false;}
void build(int l,int r,int p,T* s){
v[p].lpoint=l;v[p].rpoint=r;v[p].mul=1;
if(l==r){v[p].sum=v[p].max=v[p].min=s[l];return;}
int mid=(l+r)>>1;
build(l,mid,p*2,s);
build(mid+1,r,p*2+1,s);
v[p].sum=v[p*2].sum+v[p*2+1].sum;
v[p].max=std::max(v[p*2].max,v[p*2+1].max);
v[p].min=std::min(v[p*2].min,v[p*2+1].min);
}
void _build(int l,int r,int p,std::vector<T>&s){
v[p].lpoint=l;v[p].rpoint=r;v[p].mul=1;
if(l==r){v[p].sum=v[p].max=v[p].min=s[l];return;}
int mid=(l+r)>>1;
_build(l,mid,p*2,s);
_build(mid+1,r,p*2+1,s);
v[p].sum=v[p*2].sum+v[p*2+1].sum;
v[p].max=std::max(v[p*2].max,v[p*2+1].max);
v[p].min=std::min(v[p*2].min,v[p*2+1].min);
}
void __build(int l,int r,int p){
v[p].lpoint=l;v[p].rpoint=r;v[p].mul=1;
if(l==r){v[p].sum=v[p].max=v[p].min=0;return;}
int mid=(l+r)>>1;
__build(l,mid,p*2);
__build(mid+1,r,p*2+1);
v[p].sum=v[p].max=v[p].min=0;
}
void _add(int l,int r,T val,int p){
if(l<=v[p].lpoint&&r>=v[p].rpoint){
Cover(p);
v[p].add+=val;
v[p].sum+=val*(v[p].rpoint-v[p].lpoint+1);
v[p].max+=val;v[p].min+=val;
return;
}
Transport(p);
int mid=(v[p].lpoint+v[p].rpoint)>>1;
if(l<=mid)_add(l,r,val,p*2);
if(mid<r)_add(l,r,val,p*2+1);
v[p].sum=v[p*2].sum+v[p*2+1].sum;
v[p].min=std::min(v[p*2].min,v[p*2+1].min);
v[p].max=std::max(v[p*2].max,v[p*2+1].max);
}
void _mul(int l,int r,T val,int p){
if(l<=v[p].lpoint&&r>=v[p].rpoint){
Cover(p);
v[p].add*=val;
v[p].mul*=val;
v[p].sum*=val;
v[p].max*=val;
v[p].min*=val;
return;
}
Transport(p);
int mid=(v[p].lpoint+v[p].rpoint)>>1;
if(l<=mid)_mul(l,r,val,p*2);
if(mid<r)_mul(l,r,val,p*2+1);
v[p].sum=v[p*2].sum+v[p*2+1].sum;
v[p].min=std::min(v[p*2].min,v[p*2+1].min);
v[p].max=std::max(v[p*2].max,v[p*2+1].max);
}
void _set(int l,int r,T val,int p){
if(l<=v[p].lpoint&&r>=v[p].rpoint){
v[p].add=0;v[p].mul=1;v[p].set=val;v[p].setting=true;
v[p].sum=val*(v[p].rpoint-v[p].lpoint+1);
v[p].max=v[p].min=val;
return;
}
Transport(p);
int mid=(v[p].lpoint+v[p].rpoint)>>1;
if(l<=mid)_set(l,r,val,p*2);
if(mid<r)_set(l,r,val,p*2+1);
v[p].sum=v[p*2].sum+v[p*2+1].sum;
v[p].min=std::min(v[p*2].min,v[p*2+1].min);
v[p].max=std::max(v[p*2].max,v[p*2+1].max);
}
T _sum(int l,int r,int p){
if(l<=v[p].lpoint&&r>=v[p].rpoint)
return v[p].sum;
Transport(p);T rlt=0;
int mid=(v[p].lpoint+v[p].rpoint)>>1;
if(l<=mid)rlt+=_sum(l,r,p*2);
if(mid<r)rlt+=_sum(l,r,p*2+1);
return rlt;
}
T _max(int l,int r,int p){
if(l<=v[p].lpoint&&r>=v[p].rpoint)
return v[p].max;
Transport(p);
T rlt=-std::numeric_limits<T>::max();
int mid=(v[p].lpoint+v[p].rpoint)>>1;
if(l<=mid)rlt=std::max(_max(l,r,p*2),rlt);
if(mid<r)rlt=std::max(_max(l,r,p*2+1),rlt);
return rlt;
}
T _min(int l,int r,int p){
if(l<=v[p].lpoint&&r>=v[p].rpoint)
return v[p].min;
Transport(p);
T rlt=std::numeric_limits<T>::max();
int mid=(v[p].lpoint+v[p].rpoint)>>1;
if(l<=mid)rlt=std::min(_min(l,r,p*2),rlt);
if(mid<r)rlt=std::min(_min(l,r,p*2+1),rlt);
return rlt;
}
public:
SGT(int a,T* s){v.resize(a*4+5);build(1,a,1,s);}
SGT(int a,std::vector<T>&s){v.resize(a*4+5);_build(1,a,1,s);}
SGT(int a){v.resize(a*4+5);__build(1,a,1);}
void add(int l,int r,T val){_add(l,r,val,1);}
void mul(int l,int r,T val){_mul(l,r,val,1);}
void set(int l,int r,T val){_set(l,r,val,1);}
T sum(int l,int r){return _sum(l,r,1);}
T min(int l,int r){return _min(l,r,1);}
T max(int l,int r){return _max(l,r,1);}
/**
*构造：SMT<type>name(lenth,array);
*区间加法：name.add(lpoint,rpoint,num);
*区间乘法：name.mul(lpoint,rpoint,num);
*区间设定：name.set(lpoint,rpoint,num);
*区间和 name.sum(lpoint,rpoint);
*区间最大值 name.max(lpoint,rpoint);
*区间最小值 name.min(lpoint,rpoint);
**/
};
}
using namespace std;
using namespace extX;
inline int read(){
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
x=x*10+ch-'0',ch=getchar();
return x*f;
}
int n,q;
long long s[1000005];
int main(){
// freopen("P1253_7.in","r",stdin);
// freopen("P1253_7.ans","w",stdout);
n=read();q=read();
for(int i=1;i<=n;i++)s[i]=read();
SGT<long long>t(n,s);
for(int i=1;i<=q;i++){
int op=read();
long long x,y,k;
switch(op){
case 1:
x=read();
y=read();
k=read();
t.set(x,y,k);
break;
case 2:
x=read();
y=read();
k=read();
t.add(x,y,k);
break;
case 3:
x=read();
y=read();
cout<<t.max(x,y)<<endl;
break;
}
// cout<<op<<" succeed!\n";
}
return 0;
}封装的模板类，然后以前的东西没删，sub7~10RE（Runtime Error. Received signal 11: Segmentation fault with invalid memory reference.）
看特殊性质的话是cover的问题，但在区间加中加入Cover(p)就是全RE，否则sub7~9WA，sub10RE