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

求教

Posted by Ruandou at 2011-03-23 14:21:40 on Problem 3468
为什么我用 c++ 提交了几十遍都是 WA,
然后改用g++ 试一下却神奇般的 AC了。
#include<iostream>
using namespace std;
#include<stdlib.h>
#include<stdio.h>
typedef long long int int64;
typedef struct node
{
	int a,b;
	//long long value,bj;
	int64 value;
	int64 bj;
	int left,right;
}node;
node nodes[410000];
void create(int &num,int a,int b)
{
	int ji=num;
	nodes[ji].a=a;
	nodes[ji].b=b;
	nodes[ji].bj=0;
	nodes[ji].value=0;
	if(a<(b-1))
	{
		num++;
		nodes[ji].left=num;
		create(num,a,(a+b)/2);
		num++;
		nodes[ji].right=num;
		create(num,(a+b)/2,b);
	}
	else
	{
		nodes[ji].left=-1;
		nodes[ji].right=-1;
	}
}
void clear(int num)
{
	int a,b;
	if(nodes[num].bj!=0)
	{
		nodes[num].value+=(nodes[num].b-nodes[num].a)*nodes[num].bj;
        a=nodes[num].left;
	    b=nodes[num].right;
	    if(a!=-1&&b!=-1)
		{
	 	   //if(nodes[a].bj!=0)clear(a);
		   //if(nodes[b].bj!=0)clear(b);
		   nodes[a].bj+=nodes[num].bj;
		   nodes[b].bj+=nodes[num].bj;
		}
	    nodes[num].bj=0;
	}
}
void insert(int num,int c,int d,int64 z)
{ 
	int a,b;
	if(nodes[num].bj!=0)clear(num);
	if(c<=nodes[num].a&&d>=nodes[num].b)
	{
		nodes[num].value+=(int64)(nodes[num].b-nodes[num].a)*z;
		a=nodes[num].left;
		b=nodes[num].right;
		if(a!=-1&&b!=-1)
		{
			//clear(a);
			//clear(b);
			nodes[a].bj+=z;
			nodes[b].bj+=z;
		}
	}
	else
	{
		if(c<(nodes[num].a+nodes[num].b)/2)insert(nodes[num].left,c,d,z);
		else clear(nodes[num].left);
		if(d>(nodes[num].a+nodes[num].b)/2)insert(nodes[num].right,c,d,z);
		else clear(nodes[num].right);
		a=nodes[num].left;
		b=nodes[num].right;
		nodes[num].value=nodes[a].value+nodes[b].value;
	}
}
int64 query(int num,int c,int d)
{
	if(nodes[num].bj!=0)clear(num);
	if(c<=nodes[num].a&&d>=nodes[num].b)return nodes[num].value;
	else if(c>=(nodes[num].a+nodes[num].b)/2) return query(nodes[num].right,c,d);
	else if(d<=(nodes[num].a+nodes[num].b)/2) return query(nodes[num].left,c,d);
	else
	{
		//long long a,b;
		int64 a,b;
		a=query(nodes[num].right,c,d);
		b=query(nodes[num].left,c,d);
		return a+b;
	}
}
int main()
{
	//freopen("asimple.in","r",stdin);
	//freopen("asimple.out","w",stdout);
    int n,q,i,a,b,num=0;
	//long long ab;
	int64 ab;
	char ch;
	//cin>>n>>q;
	scanf("%d%d",&n,&q);
	create(num,0,n);
	for(i=0;i<n;i++)
	{
		scanf("%lld",&ab);
		insert(0,i,i+1,ab);
	}
	while(q--)
	{
         //cin>>ch;
		 scanf("%s",&ch);
		 switch(ch)
		 {
		 case 'C':
			 {
				 //cin>>a>>b>>c;
				 scanf("%d%d%lld",&a,&b,&ab);
				 insert(0,a-1,b,ab);
			 }break;
		 case 'Q':
			 {
				 //cin>>a>>b;
				 scanf("%d%d",&a,&b);
				 //cout<<query(0,a-1,b)<<endl;
				 printf("%lld\n",query(0,a-1,b));
			 }
			 break;
		 }
	}
	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