Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 我要吐槽，线段树一直WA,原来是lazy数组没开long long

Posted by xianmin at 2019-08-02 08:41:12 on Problem 3468
```如果一直WA,但测试数据都对，可以看看tree[N],a[N],lazy[N],ret,x有没有long long

#include<iostream>
#include<cstdio>
#include<string.h>
using namespace std;
#define N 1010000
long long tree[N],a[N];
long long lazy[N];//k++的容器，所以要long long

void sbuild(int l,int r,int p){
if(l==r) {
tree[p]=a[l];
return ;
}
int mid=(l+r)>>1;
sbuild(l,mid,p<<1);
sbuild(mid+1,r,p<<1|1);
tree[p]=tree[p<<1]+tree[p<<1|1];//设置父结点为左右子树的最大值
}
void  supdate(int L,int R,int p,int l,int r,int k){
if(L<=l&&R>=r) {
tree[p]+=k*(r-l+1);
lazy[p]+=k;
return ;
}
int mid=(l+r)>>1;
if(lazy[p]!=0){
tree[p<<1]+=(mid-l+1)*lazy[p];//为什么不*k?
tree[p<<1|1]+=(r-mid)*lazy[p];
lazy[p<<1]+=lazy[p];
lazy[p<<1|1]+=lazy[p];//标记p的下一层也已修改
lazy[p]=0;//当前标记取消
}
if(mid>=L) supdate(L,R,p<<1,l,mid,k);
if(mid+1<=R) supdate(L,R,p<<1|1,mid+1,r,k);//为什么不是<=
tree[p]=tree[p<<1]+tree[p<<1|1];
}
//查询[L,R]的信息
long long ssearch2 (int l,int r,int p,int L,int R){
if(l>=L&&r<=R) return tree[p];
int mid=(l+r)>>1;
long long ret=0;
if(lazy[p]!=0){
tree[p<<1]+=(mid-l+1)*lazy[p];//这个是干啥的？
tree[p<<1|1]+=(r-mid)*lazy[p];
lazy[p<<1]+=lazy[p];//也许是防止标记了lazy的还没运行
lazy[p<<1|1]+=lazy[p];//反正都修改完了这个就不会运行
lazy[p]=0;
}
if(mid>=L) ret+=ssearch2(l,mid,p<<1,L,R);
if(mid+1<=R) ret+=ssearch2(mid+1,r,p<<1|1,L,R);
return ret;
}
int main(){
int n,q;
scanf("%d%d",&n,&q);
for(int i=1;i<=n;i++)
scanf("%lld",&a[i]);
getchar();
sbuild(1,n,1);
while(q--){
char c;
scanf(" %c",&c);
getchar();
int b,d;
int e;
if(c=='C'){
scanf("%d%d%d",&b,&d,&e);
supdate(b,d,1,1,n,e);
}
else{
scanf("%d %d",&b,&d);
long long x=ssearch2(1,n,1,b,d);
printf("%lld\n",x);
}
}
return 0;
}```

Followed by: