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