luqyou @ 2022-10-17 15:05:45
#include<bits/stdc++.h>
#define ll long long
using namespace std;
struct node{
int l,r;
ll v,ad,xg;
}a[8000001];
ll t[4000001],sum[4000001];
int n,m;
int ls(int u){
return u<<1;
}
int rs(int u){
return (u<<1)|1;
}
void build(int u,int l,int r){
if(l==r){
a[u]=(node){l,r,t[l],0,0x3f3f3f};
return ;
}
else{
int m=l+r>>1;
build(ls(u),l,m);
build(rs(u),m+1,r);
a[u]=(node){l,r,max(a[ls(u)].v,a[rs(u)].v),0,0};
}
}
void pushup(int u){
//printf("pushuped,a[u].v fixed form %d to %d.\n",a[u].v,max(a[ls(u)].v,a[rs(u)].v));
a[u].v=max(a[ls(u)].v,a[rs(u)].v);
}
bool inrange(int L,int R,int l,int r){
return (L<=l)&&(r<=R);
}
bool outofrange(int L,int R,int l,int r){
return (R<l)||(r<L);
}
void pushdown(int u){
int L=a[u].l,R=a[u].r;
if(L==R){
return ;
}
if(a[u].xg!=0x3f3f3f3f){
int K=a[u].xg;
a[u].xg=0x3f3f3f3f;
a[ls(u)].v=K;
a[rs(u)].v=K;
a[ls(u)].xg=K;
a[rs(u)].xg=K;
}
else if(a[u].ad){
int K=a[u].ad,M=L+R>>1;
a[u].ad=0;
a[ls(u)].ad+=K;
a[rs(u)].ad+=K;
a[ls(u)].v+=K*(M-L+1);
a[rs(u)].v+=K*(R-M);
}
}
void update_ad(int u,int L,int R,ll k){
if(a[u].ad||a[u].xg){
pushdown(u);
}
int l=a[u].l,r=a[u].r;
if(inrange(L,R,l,r)){
if(a[u].xg!=0x3f3f3f){
a[u].xg+=k;
}
else{
a[u].ad+=k;
a[u].v+=k;
}
pushdown(u);
}
else if(!outofrange(L,R,l,r)){
update_ad(ls(u),L,R,k);
update_ad(rs(u),L,R,k);
pushup(u);
}
}
void update_xg(int u,int L,int R,ll k){
if(a[u].ad||a[u].xg){
pushdown(u);
}
int l=a[u].l,r=a[u].r;
if(inrange(L,R,l,r)){
if(a[u].ad){
a[u].ad=0;
}
a[u].xg=k;
a[u].v=k;
pushdown(u);
}
else if(!outofrange(L,R,l,r)){
update_xg(ls(u),L,R,k);
update_xg(rs(u),L,R,k);
pushup(u);
}
}
ll search(int u,int L,int R){
if(a[u].ad||a[u].xg){
pushdown(u);
}
int l=a[u].l,r=a[u].r;
if(inrange(L,R,l,r)){
return a[u].v;
}
else if(!outofrange(L,R,l,r)){
return max(search(ls(u),L,R),search(rs(u),L,R));
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d",&t[i]);
sum[i]=sum[i-1]+t[i];
}
build(1,1,n);
for(int i=1;i<=m;i++){
int op,x,y;
ll k;
scanf("%d",&op);
switch(op){
case 1:{
scanf("%d%d%lld",&x,&y,&k);
update_xg(1,x,y,k);
break;
}
case 2:{
scanf("%d%d%lld",&x,&y,&k);
update_ad(1,x,y,k);
break;
}
case 3:{
scanf("%d%d",&x,&y);
printf("%lld\n",search(1,x,y));
break;
}
}
//for(int u=1;u<=2*n-1;u++){
// printf(" %d %d %lld %lld %lld\n",a[u].l,a[u].r,a[u].v,a[u].ad,a[u].xg);
//}
}
return 0;
}
by Ohno @ 2022-12-10 20:58:54
@luqyou 不会是...数组开小了?