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

## 树状数组，离散化一下 ，遍历他们的顺序就好

Posted by 2017401349fei at 2018-09-26 21:58:19 on Problem 2299
```#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = 5e5+10;
int c[maxn],ord[maxn];
struct Node{
int val;
int id;
}node[maxn];
int cmp(Node a,Node b)
{
return a.val<b.val;
}
int lowbit(int x)
{
return x&(-x);
}
void update(int x)
{
while(x<=maxn-9)
{
c[x]+=1;
x+=lowbit(x);
}
}
int sum(int x)
{
int sum1=0;
while(x>0)
{
sum1+=c[x];
x-=lowbit(x);
}
return sum1;
}
int main()
{
int n;
while(~scanf("%d",&n)&&n)
{
memset(c,0,sizeof(c));
for(int i=1;i<=n;i++)
{
scanf("%d",&node[i].val);
node[i].id=i;
}
sort(node+1,node+n+1,cmp);
for(int i=1;i<=n;i++)
ord[i]=node[i].id;
long long  sum1=0;
for(int i=1;i<=n;i++)
{
update(ord[i]);
sum1+=i-sum(ord[i]);
}
cout << sum1 << endl;
}
return 0;
}
```

Followed by: