程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> hdu3015 Disharmony Trees

hdu3015 Disharmony Trees

編輯：C++入門知識

hdu3015 Disharmony Trees

Problem Description One day Sophia finds a very big square. There are n trees in the square. They are all so tall. Sophia is very interesting in them.

She finds that trees maybe disharmony and the Disharmony Value between two trees is associated with two value called FAR and SHORT.

The FAR is defined as the following:If we rank all these trees according to their X Coordinates in ascending order.The tree with smallest X Coordinate is ranked 1th.The trees with the same X Coordinates are ranked the same. For example,if there are 5 tree with X Coordinates 3,3,1,3,4. Then their ranks may be 2,2,1,2,5. The FAR of two trees with X Coordinate ranks D1 and D2 is defined as F = abs(D1-D2).

The SHORT is defined similar to the FAR. If we rank all these trees according to their heights in ascending order，the tree with shortest height is ranked 1th.The trees with the same heights are ranked the same. For example, if there are 5 tree with heights 4,1,9,7,4. Then their ranks may be 2,1,5,4,2. The SHORT of two trees with height ranks H1 and H2 is defined as S=min(H1,H2).

Two tree’s Disharmony Value is defined as F*S. So from the definition above we can see that, if two trees’s FAR is larger , the Disharmony Value is bigger. And the Disharmony value is also associated with the shorter one of the two trees.

Now give you every tree’s X Coordinate and their height , Please tell Sophia the sum of every two trees’s Disharmony value among all trees.
Input There are several test cases in the input

For each test case, the first line contain one integer N (2 <= N <= 100,000) N represents the number of trees.

Then following N lines, each line contain two integers : X, H (0 < X,H <=1,000,000,000 ), indicating the tree is located in Coordinates X and its height is H.
Output For each test case output the sum of every two trees’s Disharmony value among all trees. The answer is within signed 64-bit integer.
Sample Input

Sample Output

這道題和之前那題差不多，開兩個一維樹狀數組b1,b2，分別維護x的位置和小於等於x位置的個數。先對x，h進行離散化，用r1,r2儲存他們的名次，然後按h大小從大到小的順序依次枚舉就行了。

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
struct node{
	int x,h,r1,r2;
}a[100006];
int b1[100006],b2[100006],n;

bool cmp1(node a,node b){
	return a.x0){
		num+=b1[pos];pos-=lowbit(pos);
	}
	return num;
}

void update2(int pos,int num)
{
	while(pos<=n){
		b2[pos]+=num;pos+=lowbit(pos);
	}
}
int getsum2(int pos)
{
	int num=0;
	while(pos>0){
		num+=b2[pos];pos-=lowbit(pos);
	}
	return num;
}


int main()
{
	int m,i,j,p,t1,t2;
	__int64 sum,sum1;
	while(scanf("%d",&n)!=EOF)
	{
		for(i=1;i<=n;i++){
			scanf("%d%d",&a[i].x,&a[i].h);
			b1[i]=b2[i]=0;
		}
		sort(a+1,a+1+n,cmp1);
		a[1].r1=1;p=1;
		for(i=2;i<=n;i++){
			if(a[i].x==a[p].x){
				a[i].r1=a[p].r1;
			}
			else{
				a[i].r1=i;p=i;
			}
		}
		sort(a+1,a+1+n,cmp2);
		a[1].r2=1;p=1;
		for(i=2;i<=n;i++){
			if(a[i].h==a[p].h){
				a[i].r2=a[p].r2;
			}
			else{
				a[i].r2=i;p=i;
			}
		}
		
		sum=0;sum1=0;
		for(i=n;i>=1;i--){
			t1=getsum1(a[i].r1);
			t2=getsum2(a[i].r1);
			sum+=a[i].r2*( t2*a[i].r1-t1 + sum1-t1-(n-i-t2)*a[i].r1 );
			sum1+=a[i].r1;
			update1(a[i].r1,a[i].r1);
			update2(a[i].r1,1);
			//printf("%I64d\n",sum);
		}
		printf("%I64d\n",sum);
	}
}