3067.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

Source

Problem Id:3067  User Id:fzk 
Memory:15748K  Time:578MS
Language:C++  Result:Accepted

Source 

#include <stdio.h>
#include <memory.h>
#include <algorithm>
using namespace std;
pair<int,int> p[2000010];


const int size = 10010;

int s[size];
int m;

//清除
void clear( )
{
	memset( s, 0, sizeof s );
}

inline int lowbit(int a)
{
	return a&(a^(a-1));
}

//设置a[y] = 1; 要求y>=0
void set( int y )
{
	int j;

	y++;

	for(j=y;j<=m;j+=lowbit(j))
		s[j]++;

}

//计算a[0,y]的和; y>=0
int count(int y)
{
	int ans=0,j;
	y++;

	for(j=y;j>0;j-=lowbit(j))
		ans+=s[j];

	return ans;
}

int main( ){
	int n, i, j, t, k, l = 1, a, b;
	__int64 ans;

	scanf( "%d", &t );

	while( t-- ) {
		scanf( "%d%d%d", &a, &b, &n );
		while( a>1000 || b>1000 )
			;
		m = b+10;

		for( i=0; i<n; i++ )
			scanf( "%d%d", &p[i].first, &p[i].second );

		sort( p, p+n );
		
		p[n].first = 100000000;

		clear( );
		ans = 0;

		for( i=0; i<n; i=j ) {
			for( j=i+1; p[j].first == p[i].first; j++ )
				;
			for( k=i; k<j; k++ )
				ans += i-count( p[k].second );
			for( k=i; k<j; k++ )
				set( p[k].second );
		}

		printf( "Test case %d: %I64d\n", l++, ans );
	}

	return 0;

}