Detail of message

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

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

Posted by 1363217105 at 2011-11-09 15:54:44 on Problem 3468

#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:

> #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;
> }

Home Page Go Back To top