1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
| #include <iostream>
#include <cstdio>
using namespace std;
const int Mn(40005);
int n;
int a[Mn],t[Mn];
int mg(int l,int r)
{
if(l==r)
return 0;
else
{
int m((l+r)>>1);
int ret(0);
ret += mg(l,m); ret += mg(m+1,r);
int li(l),ri(m+1),j(l);
while(li<=m&&ri<=r)
{
if(a[li]<=a[ri]) t[j++] = a[li++];
else
{
t[j++] = a[ri++];
ret += m-li+1;
}
}
for(;li<=m;++li) t[j++] = a[li];
for(;ri<=r;++ri) t[j++] = a[ri];
for(int i(l);i<=r;++i)
a[i] = t[i];
return ret;
}
}
int main()
{
cin >> n;
for(int i(1);i<=n;++i)
{ scanf("%d",&a[i]); }
cout << mg(1,n);
return 0;
}
|