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:给一个线段树容易出错的测试用例

Posted by 18357 at 2014-05-22 18:21:18 on Problem 3468
In Reply To:给一个线段树容易出错的测试用例 Posted by:fanlonglong8500 at 2008-08-25 10:54:41
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define N 100005

typedef struct KSD
{
	int l,r;
	long long w,f;
}ksd;ksd s[N<<2];
int n,m;
void reset()
{
	memset(s,0,sizeof(s));
}
void swap(int &a,int &b){int c=a;a=b;b=c;}

void build(int note,int l,int r)
{
	int mid=(l+r)>>1;
	s[note].l=l;
	s[note].r=r;
	if(l==r)
	{
		scanf("%lld",&s[note].w);
		return ;
	}
	build(note<<1,l,mid);
	build((note<<1)+1,mid+1,r);
	s[note].w=s[note<<1].w+s[(note<<1)+1].w;
}

void et(int note)
{
	s[note].w+=(s[note].f*(s[note].r-s[note].l+1));
	if(s[note].l!=s[note].r)
	{
		s[note<<1].f+=s[note].f;
		s[(note<<1)+1].f+=s[note].f;
	}
	s[note].f=0;
}

long long noc(int note,int l,int r,int x)
{
	long long a,b;
	b=0;
	int mid=(s[note].l+s[note].r)>>1;
	et(note);
	if(l==s[note].l&&r==s[note].r)
	{
		s[note].f=x;
		return s[note].w;
	}
	//s[note].w+=(x*(r-l+1));就是它就是它,忘了这个东西的话样例能过,楼主测点过不了。 
	if(r<=mid)
	{
		a=noc(note<<1,l,r,x);
		return a;
	}
	else if(l>mid)
	{
		a=noc((note<<1)+1,l,r,x);
		return a;
	}
	else
	{
		a=noc(note<<1,l,mid,x);
		b=noc((note<<1)+1,mid+1,r,x);
		return a+b;
	}
}

char a;
int b,c,d;

void lesgo()
{
	int i,j,k;
	for(i=1;i<=m;i++)
	{
		scanf("\n%c%d%d",&a,&b,&c);
		if(b>c)swap(b,c);
		if(a=='Q')
		{
			printf("%lld\n",noc(1,b,c,0));
		}
		else
		{
			scanf("%d",&d);
			noc(1,b,c,d);
		}
	}
	return ;
}

int main()
{
	//freopen("test.in","r",stdin);
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		reset();
		build(1,1,n);
		lesgo();
	}
	return 0;
}
/*
noc函数集修改与查找于一身。
注意我注释掉的那行,会输出:
4
85
-16
-147
-122
-6
115
27
-73
7
14
21
25
57
请按任意键继续. . .
如果你们的数据跟这一样,悲伤吧,少年。
只差那一行代码,只差一行!
*/

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