hdu 3015 树状数组+离散化

浏览数：54 / 时间：2015年06月08日

#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;
struct data
{
	__int64 order;
	__int64 orign;
	__int64 rank;
};
data heigh[100100], coor[100100];
int cmp(const void *a, const void *b)
{
	return ( (*(data *)a).order - (*(data *)b).order );
}
int cmp1(const void *a, const void *b)
{
	return (*(data *)a).orign - (*(data *)b).orign;
}
/*__int64 cmp1(const void *a, const void *b)
{
	
}*/
int main()
{
	freopen("read.txt", "r", stdin);
	__int64 n;
	while(~scanf("%d", &n) )
	{
		for(int i=1; i<=n; i++)
		{
			scanf("%I64d", &coor[i].orign);
			scanf("%I64d", &heigh[i].orign);
			coor[i].order = i;
			heigh[i].order = i;
		}
		qsort(coor, n, sizeof(coor[0]), cmp1);
		qsort(heigh, n, sizeof(heigh[0]), cmp1);
		int sign1, sign2, flag1, flag2;
		sign1 = sign2 = 1;
		flag1 = coor[1].orign, flag2 = heigh[1].orign;
		for(int i=1; i<=n; i++)
		{
			if(coor[i].orign != flag1)
			{
				flag1 = coor[i].orign;
				coor[i].rank = i+1;
				sign1 = i+1;
			}
			else 
				coor[i].rank = sign1;
			if(heigh[i].orign != flag2)
			{
				flag2 = heigh[i].orign;
				heigh[i].rank = i+1;
				sign2 = i+1;
			}
			else 
				heigh[i].rank = sign2;
		}
		//qsort(coor, n, sizeof(coor[0]), cmp);
		//qsort(heigh, n, sizeof(heigh[0]), cmp);
		
		//前面是对的， 但是我不知道怎么离散化。
	}
	return 0;
}