Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 树状数组C++,为什么WA？？

Posted by zhu1650465459 at 2015-08-22 14:30:20 on Problem 2299
```#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);
}
return 0;
}
```

Followed by: