Ultra-QuickSort POJ - 2299
題目:https://vjudge.net/problem/POJ-2299
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string.h>
#include<math.h>
#include<string>
#include<vector>
#include<stack>
#include<map>
#include<set>
#include<iostream>
#include<cstdio>
#include<cstring>
#define ll long long
using namespace std;
int n;
ll ans;
const int maxn=500010;
int a[maxn];
int c[maxn];
struct node
{
int id;
int val;
}no[maxn];
int cmp(node a,node b)
{
return a.val<b.val;
}
int ask(int x)
{
int ans=0;
for(;x;x-=x&(-x))
ans+=c[x];
return ans;
}
int add(int x,int y)
{
for(;x<=n;x+=x&(-x))
{
c[x]+=y;
}
}
int main()
{
while(~scanf("%d",&n)&&n)
{
memset(c,0,sizeof(c));
memset(a,0,sizeof(a));
ans=0;
for(int i=1;i<=n;i++)
{
scanf("%d",&no[i].val);
no[i].id=i;
}
sort(no+1,no+1+n,cmp);
for(int i=1;i<=n;i++)
{
a[no[i].id]=i;
}
for(int i=n;i;i--)
{
ans+=ask(a[i]-1);
add(a[i],1);
}
printf("%lld\n",ans);
}
}