POJ 2299 Ultra - QuickSort (트 리 배열 역순 구)

http://poj.org/problem?id=2299
나무 모양 의 배열 로 역 서 수 를 구 하 는 것 은 선분 나무 로 역 서 수 를 구 하 는 방법 과 유사 하 다.91054 를 입력 하면 C [i] 트 리 배열 의 구축 은 0, 1, 2, 3, 4, 5, 6, 79 배열 1, 0, 1, 0, 1, 0, 0, 1 을 표시 합 니 다.그래서 둘 다 이산 화가 필요 하 다.그리고 대충 생각 은 업 데 이 트 를 하면 서 값 을 구 하 는 거 예요.

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long LL;

const int N = 500000 + 100;
long long a[N],b[N];
long long n;
long long tr[N];
long long lowbit(long long x)
{
    return x & (-x);
}
void update(long long pos,long long val)
{
    while(pos<=n)
    {
        tr[pos] += val;
        pos += lowbit(pos);
    }
    return;
}
long long query(long long x)
{
    long long sum = 0;
    while(x)
    {
        sum += tr[x];
        x -= lowbit(x);
    }
    return sum;
}
long long solve()
{
    long long res = 0;
    for(long long i = n;i>=1;i--)
    {
        long long x = lower_bound(b+1,b+1+n,a[i])-(b+1) + 1;
        res += query(x-1);
        update(x,1);
    }
    return res;
}
int main()
{
    while(~scanf("%lld",&n) && n) 
    {
        memset(tr,0,sizeof(tr));
        memset(a,0,sizeof(a));
        memset(b,0,sizeof(b));
        for(long long i=1;i<=n;i++)
            scanf("%lld",&a[i]),b[i] = a[i];
        sort(b+1,b+1+n);
        printf("%lld
",solve());
    }
    return 0;
}