[C++] 純文本查看 復制代碼
#include <stdio.h>
#include <string.h>
typedef long long ll;
int bit[20000010];
int N;
int sum(int x)
{
int s=0;
while(x>0)
{
s+=bit[x];
x-=x&(-x);
}
return s;
}
void add(int x,int d)
{
while(x<=N)
{
bit[x]+=d;
x+=x&(-x);
}
}
int main()
{
memset(bit,0,sizeof(bit));
scanf("%d",&N);
ll ans=0;
for(int i=0;i<N;i++)
{
int index;
scanf("%d",&index);
ans+=(ll)i-(ll)sum(index);
add(index,1);
}
printf("%lld\n",ans);
return 0;
}
[C++] 純文本查看 復制代碼
#include <iostream>
using namespace std;
int data[2000000+1];
int temp[2000000+1];
long long merge(int p, int m, int q)
{
int idx_L = p;
int idx_R = m + 1;
int idx_temp = p;
long long cnt = 0;
while (idx_L <= m && idx_R <= q) {
if (data[idx_L] <= data[idx_R]) {
temp[idx_temp++] = data[idx_L++];
}
else {
temp[idx_temp++] = data[idx_R++];
cnt += (m - idx_L + 1); // 記算逆序數對數
}
}
while (idx_L <= m)
temp[idx_temp++] = data[idx_L++];
while (idx_R <= q)
temp[idx_temp++] = data[idx_R++];
for (int i=p; i<=q; i++)
data = temp;
return cnt;
}
long long merge_sort(const int p, const int q)
{
if (p >= q) return 0;
int m = (p+q) / 2;
long long cnt_L = merge_sort(p, m);
long long cnt_R = merge_sort(m+1, q);
long long cnt_M = merge(p, m, q);
return (cnt_L + cnt_R + cnt_M);
}
int main()
{
int N;
cin >> N;
for (int i=0; i<N; i++)
cin >> data;
long long cnt = merge_sort(0, N-1);
cout << cnt << endl;
return 0;
}
