3109.txt

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

Source

Problem Id:3109  User Id:fzk 
Memory:3176K  Time:2179MS
Language:G++  Result:Accepted

Source 

#include <stdio.h>
#include <memory.h>
#include <algorithm>

using namespace std;

const int size = 100010;

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]++;

}

void reset( 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;
}


pair<int,int> q[size*2];
pair<int,int> p[size];
int f[100010];

int main( ) {
	int i, j, k, n, t, ans = 0, N, h;
 
	scanf( "%d", &n ); 
	for( i=0; i<n; i++ )
		scanf( "%d%d", &p[i].first, &p[i].second );

	sort( p, p+n );

	k = 0;
	h = 0;
	for( i=0; i<n; i=j ) {
		for( j=i+1; j<n && p[j].first == p[i].first; j++ )
			;
		f[h++] = p[i].first;
	
		q[k].first = p[i].second;
		q[k++].second = ((p[i].first)<<1);
		q[k].first = p[j-1].second+1;
		q[k++].second = ((p[i].first)<<1)|1;
	}
	m = h;
	N = k;

	for( i=0; i<n; i++ )
		swap( p[i].first, p[i].second );

	sort( p, p+n );
	sort( q, q+N );

	k = 0;
	for( i=0; i<n; i=j ) {
		for( j=i+1; j<n && p[j].first == p[i].first; j++ )
			;
		
		while( k < N && q[k].first <= p[i].first ) {
			t = lower_bound( f, f+m, q[k].second>>1 ) - f;
			if( q[k].second&1 )
				reset( t );
			else
				set( t );
			k++;
		}
		ans += count( lower_bound( f, f+m, p[j-1].second ) - f ) 
			- count( lower_bound( f, f+m, p[i].second ) - f-1 );
	}

	printf( "%d\n", ans );
	return 0;
}