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:树状数组C++,为什么WA??

Posted by jugggg at 2017-11-26 14:45:31 on Problem 2299
In Reply To:树状数组C++,为什么WA?? Posted by:zhu1650465459 at 2015-08-22 14:30:20
> #include<cstdio>
> #include<iostream>
> #include<cstring>
> #include<cstdlib>
> using namespace std;
> struct node
> {
> 	int x,y;
> }a[500005];
> int l[500005],r[500005],n;
> int cmp(const void *x1,const void *x2)
> {
> 	node n1=*(node *)x1;
> 	node n2=*(node *)x2;
> 	if(n1.x!=n2.x) return n1.x-n2.x;
> 	else return n1.y-n2.y;
> }
> int lowbit(int x)
> {
> 	return x & -x;
> }
> void gaibian(int x)
> {
> 	while (x<=n)
> 	{
> 		l[x]+=1;
> 		x+=lowbit(x);
> 	}
> }
> int qiuhe(int x)
> {
> 	int ans=0;
> 	while(x>0)
> 	{
> 		ans+=l[x];
> 		x-=lowbit(x);
> 	}
> 	return ans;
> }
> int main()
> {
> 	int i; long long ans=0;
> 	while(scanf("%d",&n)!=EOF)
> 	{
> 		if(n==0) break;
> 		for(i=1;i<=n;i++) 
> 		{
> 			scanf("%d",&a[i].x);
> 			a[i].y=i;
> 		}
> 		qsort(a+1,n,sizeof(node),cmp);
> 		for(i=1;i<=n;i++) r[a[i].y]=i;
> 		for(i=1;i<=n;i++) l[i]=0;
> 		for(i=1;i<=n;i++)
> 		{
> 			gaibian(r[i]);
> 			ans+=i-qiuhe(r[i]);
> 		}
> 		printf("%I64d\n",ans);  这个地方可能要用 printf("%lld", ans); 我之前的答案就是因为 printf("%d", ans)出错的。可能对你有帮助!!
> 	}
> 	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