Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  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:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator