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

Re:这道3468题希望有人帮我看看,我是初学线段树的,这道题做了好久了,但是addnew更新哪里总有错误,愁死了,江湖救急,大家帮帮忙

Posted by liaoruo at 2012-02-28 23:12:55 on Problem 3468
In Reply To:这道3468题希望有人帮我看看,我是初学线段树的,这道题做了好久了,但是addnew更新哪里总有错误,愁死了,江湖救急,大家帮帮忙 Posted by:1363217105 at 2011-11-09 15:54:44
> #include<iostream>
> using namespace std;
> 
> #define MAXM 100000
> 
> struct 
> {
> 	int l,r;
> 	 __int64 sum,crease;//超过整数的范围
> }tree[MAXM*4+1];
> 
> void build(int left,int right,int num)
> {
> 	 int d;
>      tree[num].l=left;tree[num].r=right;
> 	 if(tree[num].l==tree[num].r){ tree[num].crease=0;cin>>d;tree[num].sum=d;return;}
> 	 int mid=(tree[num].l+tree[num].r)>>1;
> 	 build(tree[num].l,mid,num<<1);
> 	 build(mid+1,tree[num].r,num<<1|1);
> 	 tree[num].sum=tree[num<<1].sum+tree[num<<1|1].sum;
>      tree[num].crease=0;
> }
> 
> int query(int left,int right,int num)
> {
>      if(left==tree[num].l&&tree[num].r==right)return tree[num].sum;
> 	 int mid=(tree[num].l+tree[num].r)>>1;
> 	 if(right<=mid)return query(left,right,num<<1);
> 	 else if(mid<left)return query(left,right,num<<1|1);
> 	 else return (query(left,mid,num<<1)+query(mid+1,right,num<<1|1));
> }
> 
> void addnew(int left,int right,int add,int num)
> {
>     if(tree[num].l==left&&tree[num].r==right)
> 	{tree[num].crease+=add;return;}
>     int mid=(tree[num].l+tree[num].r)>>1;
> 	if(right<=mid) addnew(left,right,add,num<<1);
> 	else if(mid<left) addnew(left,right,add,num<<1|1);
> 	else 
> 	{
> 		addnew(left,mid,add,num<<1);
> 		addnew(mid+1,right,add,num<<1|1);
> 	}
> 	tree[num].sum=tree[num<<1].sum+tree[num<<1].crease*(tree[num<<1].r-tree[num<<1].l+1);
> 	tree[num].sum+=tree[num<<1|1].sum+tree[num<<1|1].crease*(tree[num<<1|1].r-tree[num<<1|1].l+1);
> }
> 
> int main()
> {
> 	int N,M,i,j,p;
> 	char c;
> 	cin>>N>>M;
> 	build(1,N,1);
> 	for(int k=0;k<M;k++) 
> 	{
> 		 scanf("%c",&c);
> 		 if(c=='Q')
> 		 {
> 			 
> 			 scanf("%d%d",&i,&j);
> 			 printf("%d\n",query(i,j,1));
> 				 
> 		 }
>          else
> 		 {
> 			 scanf("%d%d%d",&i,&j,&p);
>              addnew(i,j,p,1);
> 		 }
> 	}
> 	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