C++11(clang++ 3.9) 解法, 执行用时: 127ms, 内存消耗: 5736K, 提交时间: 2019-03-16 13:14:40

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int n, tail, ans, C[100001];
struct LSH{ int x, id; } lsh[100001];
struct Poi{ int x, y; } p[100001];
struct Seg{int k, l, r, y;} seg[1000001];
bool cmp0( const LSH &a, const LSH &b ) { return a.x < b.x; }
bool cmp1( const Poi &a, const Poi &b ) { 
    if( a.x != b.x ) return a.x < b.x; 
    else             return a.y < b.y;
}
bool cmp2( const Poi &a, const Poi &b ) { 
    if( a.y != b.y ) return a.y < b.y; 
    else             return a.x < b.x;
}
bool cmp3( const Seg &a, const Seg &b ) { 
    if( a.y != b.y ) return a.y < b.y; 
    else             return a.k < b.k;  
}
void add_line( int k, int l, int r, int t ) { 
    if( !k ) { seg[++tail].l = l; seg[tail].y = t; seg[tail].r = r; } //线段 
    else {//点 
        seg[++tail].l = t; seg[tail].y = l; seg[tail].k = 1;
        seg[++tail].l = t; seg[tail].y = r; seg[tail].k = -1;
    }
}
void build( ) {
    sort( p + 1, p + n + 1, cmp1 );
    for( register int i = 2; i <= n; i++ ) 
        if( p[i].x == p[ i - 1 ].x ) add_line( 1, p[ i - 1 ].y, p[i].y, p[i].x );
    sort( p + 1, p + n + 1, cmp2 );
    for( register int i = 2; i <= n; i++ ) 
        if( p[i].y == p[ i - 1 ].y ) add_line( 0, p[ i - 1 ].x, p[i].x, p[i].y );
}
void modify( int x, int y ) { for( ; x <= n ; x += x & -x ) C[x] += y; }
int query( int x ) { int tmp = 0; for( ; x; x -= x & -x ) tmp += C[x]; return tmp; }
void solve( ) {
    for( register int i = 1; i <= tail; i++ ) {
        if( !seg[i].k ) ans += query( seg[i].r - 1 ) - query( seg[i].l );
        else            modify( seg[i].l, seg[i].k );
    }
}
int main( ) {
    scanf( "%d", &n );
    for( register int i = 1; i <= n; i++ ) {
        scanf( "%d%d", &p[i].x, &p[i].y );
        lsh[i].x = p[i].x;
        lsh[i].id = i;
    }
    sort( lsh + 1, lsh + n + 1, cmp0 ); int cnt = 0;
    lsh[0].x = -2147483640;
    for( register int i = 1; i <= n; i++ ) {
        if( lsh[i].x != lsh[ i - 1 ].x ) cnt++;
        p[lsh[i].id].x = cnt;
    }
    build();
    sort( seg + 1, seg + tail + 1, cmp3 );
    solve();
    printf( "%d", ans + n );
    return 0;
}