http://poj.org/problem?id=3109
#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( "%dn", ans );
return 0;
}