头部背景图片
Decaku 's Blog |
Decaku 's Blog |

Poj 2299

描述:

求一段序列的逆序数对的个数。


思路:

和归并排序思路类似,使用树状数组时注意稳定排序。


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
41
42
43
44
45
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

const int maxn=5e5+5;
typedef long long ll;
int a[maxn];
int c[maxn];
ll ans;

inline void solve(int l,int r)
{
if(l==r) return;
int mid=(l+r)>>1;
solve(l,mid);
solve(mid+1,r);
int i=l,j=mid+1,k=l;
while(i<=mid&&j<=r)
{
if(a[i]<=a[j])
c[k++]=a[i++];
else c[k++]=a[j++],ans+=mid-i+1;
}

while(i<=mid) c[k++]=a[i++];
while(j<=r) c[k++]=a[j++];

for(int i=l; i<=r; i++)
a[i]=c[i];
}

int main()
{
int n;
while(~scanf("%d",&n)&&n>0)
{
ans=0;
for(int i=1; i<=n; i++)
scanf("%d",&a[i]);
solve(1,n);
printf("%lld\n",ans);
}
return 0;
}
avatar Decaku 很菜但也很想carry