ツリー配列の離散化Ultra-QuickSort

離散化するが、データ範囲が大きすぎるのは借りた利器であり、例を挙げると、4つの数99999991 123,1583のデータ範囲が大きすぎて、木状配列の中のc配列が開いている範囲がデータの範囲であり、この場合には離散化が必要である.4つの数を一度に1 2 3 4(すなわち1番目の数、2番目の数...)と表記し、キー値を並べ替えた後は2 3 4 1(すなわち小さいから大きいまで2番目の数、3番目の数...)の順であるため、2番目の数は最小、すなわちf[2]=1、f[3]=2、f[4]=3、f[1]である=4、つまりキー値を1~nに変えても相対的な大きさは変わらない、すなわち4 1 2 3である.例えば、元の4つの数の逆シーケンスの総和が要求され、現在は4 1 2 3の逆シーケンスの総和を求め、空間圧力を大幅に節約している(ツリー配列の長さはデータ範囲)

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define MAX 500004
int c[MAX],f[MAX];
struct lisan{
	int v,num;
}a[MAX];
int get_val()
{     
    int ret(0);     
    char c;     
    while((c=getchar())==' '||c=='
'||c=='\r');     
        ret=c-'0';     
    while((c=getchar())!=' '&&c!='
'&&c!='\r')                 
            ret=ret*10+c-'0';     
        return ret;
}
int cmp(lisan a,lisan b)
{
	return a.v<b.v;
}
int n;
int lowbit(int x)
{
	return x&(-x);
}
void update(int x,int num)
{
	while(x<=n)
	{
		c[x]+=num;
		x+=lowbit(x);
	}
}
int get_sum(int x)
{
	int s=0;
	while(x>=1)
	{
		s+=c[x];
		x-=lowbit(x);
	}
	return s;
}
int main()
{
	int i;
	while(scanf("%d",&n),n)
	{
		memset(c,0,sizeof(c));
		for(i=1;i<=n;i++)
		{
			a[i].v=get_val();
			a[i].num=i;
		}
		sort(a+1,a+1+n,cmp);
        for(i=1;i<=n;i++)
			f[a[i].num]=i;
		__int64 sum=0;
		for(i=1;i<=n;i++)
		{
			update(f[i],1);
			sum+=i-get_sum(f[i]);
		}
		printf("%I64d
",sum);
	}
	return 0;
}