WA了三个点,关键是错误样例我本地测没问题
#include<bits/stdc++.h>
using namespace std;
#define MAXN 100001
typedef long long ll;
int n,m;
ll d[MAXN];
__int128 di[MAXN];
ll lowbit(ll x){
return x&(-x);
}
void update(int pos,ll num){//用树状数组维护 差 和 差*i
d[pos]+=num;
ll v=pos*num;
di[pos]+=v;
while(pos+lowbit(pos)<=n){
pos+=lowbit(pos);
d[pos]+=num;
di[pos]+=v;
}
}
__int128 sum(int pos){
__int128 ans=0;
for(int i=pos;i>=1;i-=lowbit(i)){
ans+=(pos+1)*d[i]-di[i];//带入公式,公式附在图里
}
return ans;
}
inline void write(__int128 x){//快写
if(x/10) write(x/10);
putchar((x%10)^48);
return ;
}
int main(){
scanf("%d%d",&n,&m);
ll a=0,b=0;
for(int i=1;i<=n;i++){//反正存差分,只要上一个和这一个就行
swap(a,b);//使a的值成为当前输入的上一个的值
scanf("%lld",&b);
update(i,b-a);//更新差分
}
while(m--){
int type,l,r,k;
scanf("%d",&type);
if(type==1){
scanf("%d%d%d",&l,&r,&k);
update(l,k);//区间修改
update(r+1,-k);
}
else{
scanf("%d%d",&l,&r);
__int128 res= sum(r)-sum(l-1);//区间查询
if(res<0){//__int128 的输出
printf("-");
res*=-1;
}
write(res);
printf("\n");
}
}
return 0;
}

思路来源: