poj 2299 离散化+树状树状数组

题目链接：Ultra-QuickSort

题解：把每个数的逆序数的个数加入答案，然后由于a的数过大，离散化到小范围就可以。

//#include<bits/stdc++.h>
#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
#define pb push_back
#define ll long long
#define PI 3.14159265
#define ls l,m,rt<<1
#define rs m+1,r,rt<<1|1
#define eps 1e-7
using namespace std;
const int maxn=5e5+100;
int n,q;
ll bit1[maxn];
struct node
{
    ll x,id;
}a[maxn];
int aa[maxn];
bool cmp(const node x,const node y)
{
    return x.x<y.x;
}
ll lowbit(int x)
{
    return x&(-x);
}
void add(ll *b,ll x,ll y)
{
    if(x==0)x=1;
    for(int i=x;i<=n;i+=lowbit(i))
    {
        b[i]+=y;
    }
}
ll get_sum(ll *b,int x)
{
    ll ans=0;
    for(int i=x;i>0;i-=lowbit(i))
    {
        ans+=b[i];
    }
    return ans;
}
int main()
{
	std::ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	while(cin>>n)
    {
        if(!n)break;
        for(int i=0;i<n;i++)
        {
            cin>>a[i].x;
            a[i].id=i;
        }
        sort(a,a+n,cmp);
        ll ans=0;
        for(int i=0;i<n;i++)
        {
            aa[a[i].id]=i;
        }
        memset(bit1,0,sizeof(bit1));
        for(int i=0;i<n;i++)
        {
            ans+=i-get_sum(bit1,aa[i]);
            add(bit1,aa[i],1);
        }
        cout<<ans<<'
';
    }
	return 0;
 }