# Poj Solution 3109

```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;
}

```
This entry was posted in poj. Bookmark the permalink.