卷王 @ 2022-08-13 18:41:34
#include<bits/stdc++.h>
#pragma GCC optimize(2)
#define maxn 1000001
#define INF 1e10
using namespace std;
typedef long long ll;
ll t1[maxn*4],t2[maxn*4],w[maxn*4],a[maxn]; //t1记录区间赋值为x,t2记录区间要加上x。
int opt,n,q,l,r,k;
//=======================================================================
inline void write(int x)
{
if(x<0){putchar('-');x=-x;}
if(x>9)write(x/10);
putchar(x%10+'0');
}
inline ll read()
{
ll 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<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*f;
}
//=======================================================================
inline void push_up(int u) {w[u]=max(w[u<<1],w[u<<1|1]);}
inline bool in_range(int L,int R,int l,int r) {return (L>=l)&&(R<=r);}
inline bool outof_range(int L,int R,int l,int r) {return (L>r)||(R<l);}
inline void maketag1(int u,ll x) {w[u]=x; t1[u]=x; t2[u]=0;}
inline void build(int u,int L,int R)
{
if(L==R) { w[u]=a[L]; return ;}
int mid=(L+R)>>1;
build(u,L,mid); build(u,mid+1,R);
push_up(u);
}
inline void maketag2(int u,ll x)
{
w[u]+=x;
if(t1[u]!=INF) t1[u]+=x;
else t2[u]+=x;
}
inline void pushdown(int u)
{
if(t1[u]!=INF)
{
maketag1(u<<1,t1[u]);
maketag1(u<<1|1,t1[u]);
t1[u]=INF;
}
else if(t2[u]!=0)
{
maketag2(u<<1,t2[u]);
maketag2(u<<1|1,t2[u]);
t2[u]=0;
}
}
inline ll query(int u,int L,int R,int l,int r)
{
if(in_range(L,R,l,r)) return w[u];
else if(!outof_range(L,R,l,r))
{
int mid=(L+R)/2;
pushdown(u);
return query(u<<1,L,mid,l,r)+query(u<<1|1,mid+1,R,l,r);
}
else return 0;
}
inline void update(int u,int L,int R,int l,int r,int opt,ll x)
{
if(in_range(L,R,l,r))
{
if(opt==1) maketag1(u,x);
else maketag2(u,x);
}
else if(outof_range(L,R,l,r))
{
int mid=(L+R)>>1;
pushdown(u);
update(u,L,mid,l,r,opt,x);
update(u,mid+1,R,l,r,opt,x);
push_up(u);
}
}
int main()
{
n=read(),q=read();
for(int i=1;i<=n;i++) a[i]=read();
build(1,1,n);
for(int i=1;i<=q;i++)
{
scanf("%d %d %d",&opt,&l,&r);
if(opt==1 || opt==2)
{
k=read();
update(1,1,n,l,r,opt,k);
}
else printf("%ld\n",query(1,1,n,l,r));
}
return 0;
}
程序输出:
0
0
-1
样例输出:
7
6
-1