树状数组
Ultra-QuickSort
先离散化处理在利用树状数组求一个数前面比他小的。
#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<stack>
#include<queue>
#include<cstdlib>
#include<string>
#include<vector>
#include<list>
#include<map>
#include<set>
#define fi first
#define se second
#define pb push_back
#define me(a,b) memset(a,b,sizeof(a))
#define INIT() std::ios::sync_with_stdio(false)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int>P;
const int MAX_N=500000+5;
const int MAX_M=100000+5;
const int INF=0x7fffffff;
const int inf=1000000000;
const double EPS=1e-6;
const ull base=123;
const ll mod=998244353;
const double pi=4*atan(1.0);
struct node
{
int pos;
int x;
int cnt;
} a[MAX_N];
int n;
int bit[MAX_N];
bool cmp(node a,node b)
{
return a.x<b.x;
}
bool cmp2(node a,node b)
{
return a.pos<b.pos;
}
int sum(int x)
{
int s=0;
while(x>0)
{
s+=bit[x];
x-=x&-x;
}
return s;
}
void add(int x,int val)
{
while(x<=n)
{
bit[x]+=val;
x+=x&-x;
}
}
int main()
{
while(cin>>n&&n)
{
me(bit,0);
int i;
for(i=1; i<=n; i++)
{
a[i].pos=i;
scanf("%d",&a[i].x);
}
sort(a+1,a+1+n,cmp);
int cnt=1;
a[1].cnt=1;
for(i=2; i<=n; i++)
{
a[i].cnt=i;
}
sort(a+1,a+1+n,cmp2);
ll ans=0;
for(i=1; i<=n; i++)
{
add(a[i].cnt,1);
ans+=(ll)(i-sum(a[i].cnt));
}
cout<<ans<<endl;
}
}