BZOJ - 3262 陌上花开 CDQ分治 三维偏序

大家都很强， 可与之共勉 。

三维偏序裸题。。。
某ZYC同学说什么代码都一样，只是比我慢了1.3s而已，而已。

/**************************************************************
    Problem: 3262
    User: Lazer2001
    Language: C++
    Result: Accepted
    Time:1684 ms
    Memory:4488 kb
****************************************************************/

# include <bits/stdc++.h>

# define RG register
# define __inline __attribute__( ( always_inline ) )

char buf [1 << 16], *ss, *tt ;

inline char pick ( )  {
    return ( ss == tt ) ? ( tt = buf + fread ( ss = buf, 1, 1 << 16, stdin ), *ss ++ ) : *ss ++ ;
}

template < class T >
__inline void readIn ( T& x )  {
    register char ch ;
    while ( ! isdigit ( ch = pick ( ) ) ) ;
    for ( x = -48 + ch ; isdigit ( ch = pick ( ) ) ; x = x * 10 + ch - 48 ) ;
}

const int N = 100005 ;

class Bit  {
private :
    int *c, n, rt ;
public :
    Bit ( ) {   }
    Bit ( int n )  {
        this -> n = n ;
        c = new int [n + 1] ;
        memset ( c, 0, sizeof ( int ) * ( n + 1 ) ) ;
    }

    __inline void Modify ( int pos, int x )  {
        while ( pos <= n )  c [pos] += x, pos += ( pos & -pos ) ;
    }

    __inline int Query ( int pos )  {
        for ( rt = 0 ; pos ; pos -= ( pos & -pos ) )    rt += c [pos] ;
        return rt ;
    }
} T ;

int n, k, qcnt ;

struct Px  {
    int x, y, z ;
    int cnt, ans ;
    __inline bool operator == ( const Px& rhs )  const  {
        return ( x == rhs.x ) && ( y == rhs.y ) && ( z == rhs.z ) ;
    }
} a [N] ;

__inline bool cmp1 ( const Px& a, const Px& b )  {
    if ( a.x ^ b.x )    return a.x < b.x ;
    if ( a.y ^ b.y )    return a.y < b.y ;
    return a.z < b.z ;
}

__inline bool cmp2 ( const Px& a, const Px& b )  {
    if ( a.y ^ b.y )    return a.y < b.y ;
    return a.z < b.z ;
}

inline void Cdq ( int l, int r )  {
    if ( l == r )  {
        a [l].ans += a [l].cnt - 1 ;
        return ;
    }
    int mid = ( l + r ) >> 1 ;
    Cdq ( l, mid ) ;  Cdq ( mid + 1, r ) ;
    std :: sort ( a + l, a + mid + 1, cmp2 ) ;
    std :: sort ( a + mid + 1, a + r + 1, cmp2 ) ;
    RG int i, j, k ;
    for ( i = mid + 1, j = l ; i <= r ; ++ i )  {
        while ( j <= mid && a [j].y <= a [i].y )  {
            T.Modify ( a [j].z, a [j].cnt ) ;
            ++ j ;
        }
        a [i].ans += T.Query ( a [i].z ) ;
    }
    for ( k = l ; k ^ j ; ++ k )    T.Modify ( a [k].z, - a [k].cnt ) ;
}

int ans [N] ;

int main ( )  {
    readIn ( n ) ; readIn ( k ) ;
    T = Bit ( k ) ;
    for ( RG int i = 1 ; i <= n ; ++ i )  {
       readIn ( a [i].x ) ; readIn ( a [i].y ) ; readIn ( a [i].z ) ;
        a [i].ans = 1 ;
    }
    std :: sort ( a + 1, a + 1 + n, cmp1 ) ;
    a [qcnt = 1].cnt = 1 ;
    for ( RG int i = 2 ; i <= n ; ++ i )  {
        if ( a [i] == a [i - 1] )   ++ a [qcnt].cnt ;
        else a [++ qcnt] = a [i], a [qcnt].cnt = 1 ;
    }
    Cdq ( 1, qcnt ) ;
//    std :: sort ( a + 1, a + 1 + qcnt, cmp1 ) ;
    for ( RG int i = 1 ; i <= qcnt ; ++ i )  {
        ans [a [i].ans] += a [i].cnt ;
    }
    for ( RG int i = 1 ; i <= n ; ++ i )   {
        printf ( "%d\n", ans [i] ) ;
    }
}