我开longlong了啊???
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL N=1e5+10;
LL tree[4*N],a[N],add[N],n;
void build(LL l,LL r,LL k){//l:左端点 r:右端点 k:节点编号
if(l==r){//如果是叶子节点(叶子节点的左右端点相等,即长度为1)
tree[k]=a[l];//赋值
return;
}
LL mid=(l+r)>>1;//取中间值
build(l,mid,2*k);//拆分左子树
build(mid+1,r,2*k+1);//拆分右子树
tree[k]=tree[2*k]+tree[2*k+1];//pushup:回溯时利用子节点更新父节点(此处维护最大值)
}
void change(LL k,LL l,LL r,LL v){//修改一个节点
tree[k]+=v*(r-l+1);//修改值
add[k]+=v;//标记
}
void down(LL k,LL l,LL r){//标记下放
if(add[k]!=0){
LL mid=(l+r)>>1;
change(k*2,l,mid,add[k]);//下放到左孩子
change(k*2+1,mid+1,r,add[k]);//下放到右孩子
add[k]=0;//父节点标记清空
}
}
void update(LL k,LL l,LL r,LL x,LL y,LL v){//把节点p的值改为x l:左端点 r:右端点 k:当前节点编号
if(l>=x && r<=y){
change(k,l,r,v);
return;
}
down(k,l,r);
LL mid=(l+r)>>1;
if(x<=mid) update(2*k,l,mid,x,y,v);//左子树
if(y>mid) update(2*k+1,mid+1,r,x,y,v);//右子树
tree[k]=tree[2*k]+tree[2*k+1];
}
LL quary(LL k,LL l,LL r,LL x,LL y){//查询x到y的区间最大值
if(l>=x && r<=y){//如果当前的区间完全包含在查询区间中时,不需要继续递归
return tree[k];
}
down(k,l,r);
LL mid=(l+r)>>1;
LL res=0;
if(x<=mid){//左区间有覆盖
res+=quary(2*k,l,mid,x,y);
}
if(y>mid){//右区间有覆盖
res+=quary(2*k+1,mid+1,r,x,y);
}
return res;
}
LL m;
int main(){
cin>>n>>m;
for(LL i=1;i<=n;i++){
cin>>a[i];
}
build(1,n,1);
for(LL i=1;i<=m;i++){
LL t;
cin>>t;
if(t==1){
LL x,y,k;
cin>>x>>y>>k;
update(1,1,n,x,y,k);
}else{
LL x,y;
cin>>x>>y;
cout<<quary(1,1,n,x,y)<<endl;
}
}
return 0;
}