献上丑陋的代码~~自我感觉函数写的没问题但样例都过不了
#include<bits/stdc++.h>
#define int long long
using namespace std;
#define N 2000005
int n,a[N],sum[N<<2],mx[N<<2];//四倍空间;
bool tag[N<<2];
inline int ls(int x){
return x<<1;
}
inline int rs(int x){
return x<<1|1;
}
inline void add(int x,int l,int r,int k){
sum[x]+=k*(l-r+1);
mx[x]+=k;
tag[x]+=k;
}
inline void pushup(int x){//左二子+右二子 =自己
//通过儿子找自己
sum[x]=sum[ls(x)]+sum[rs(x)];
mx[x]=max(mx[ls(x)],mx[rs(x)]);
}
inline void pushdown(int x,int l,int r){
int m=(l+r)>>1;
pushdown(x,l,r);
// if(tag[x]!=0){
add(ls(x),l,m,tag[x]);
add(rs(x),m+1,r,tag[x]);
// }
tag[x]=0;
}
inline void build(int x,int l,int r){
if(l==r){
sum[x]=mx[x]=a[l];
return ;
}
// pushdown(x,l,r);
int m =(l+r)>>1;
build(ls(x),l,m);
build(rs(x),m+1,r);
pushup(x);
}
inline int querySum(int x,int l,int r,int L,int R){
//查询区间
//x:当前节点编号
//l,r:当前节点维护的区间
//L,R:询问的区间
if(L<=l&&r<=R){
return sum[x];
}
pushdown(x,l,r);
int m=(l+r)>>1;
int ret=0;
if(L<=m)ret+=querySum(ls(x),l,m,L,R);//甩给左儿子
if(m<R)ret+= querySum(rs(x),m+1,r,L,R);//甩给右儿子
return ret;
}
inline int queryMax(int x,int l,int r,int L,int R){
if(L<=l&&r<=R){
return mx[x];
}
pushdown(x,l,r);
int m=(l+r)>>1;
int ret=-299999999999;
if(L<=m)ret=max(ret,queryMax(ls(x),l,m,L,R));//甩给左儿子
if(m<R)ret=max(ret,queryMax(rs(x),m+1,r,L,R));//甩给右儿子
return ret;
}
inline void qjj(int x,int l,int r,int L,int R,int k){//区间加
if(L<=l&&r<=R){
return add(x,l,r,k);
}
pushdown(x,l,r);
int m=(l+r)>>1;
if(L<=m)qjj(ls(x),l,m,L,R,k);
if(m<R)qjj(rs(x),m+1,r,L,R,k);
pushup(x);
}
inline void posAdd(int x,int l,int r,int p,int k){
//单点修改
//x:当前节点编号
//l,r:当前节点维护的区间
//L,R:询问的区间
sum[x]+=k;
if(l==r)return ;
pushdown(x,l,r);
int m=(l+r)>>1;
if(p<=m)posAdd(ls(x),l,m,p,k);
else posAdd(rs(x), m + 1, r, p, k);
}
signed main(){
int m;
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
}
build(1,1,n);
while(m--){
char xx;
cin>>xx;
int x,y;
cin>>x>>y;
if(xx=='1'){
int k;
cin>>k;
qjj(1,x,y,1,n,k);
}
else{
cout<<querySum(1,x,y,1,n)<<'\n';
}
}
return 0;
}
~~