Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
我要吐槽,线段树一直WA,原来是lazy数组没开long long如果一直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: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator