题目：
http://www.lydsy.com/JudgeOnline/problem.php?id=2648
http://www.lydsy.com/JudgeOnline/problem.php?id=2716
嘛。。。其实2716可以CDQ分治+BIT或者树套树水掉的，无奈代码量太大不敢写，于是就去搞了k-d树。。。结果搞了整整一天才调好。。。（偷懒的后果。。。）（话说BZOJ终于破500了好开心！~~）
代码：
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <map>
using namespace std ;
#define REP( i , l , r ) for ( int i = l ; i <= r ; ++ i )
#define rep( i , x ) for ( int i = 0 ; i ++ < x ; )
#define Rep( i , x ) for ( int i = 0 ; i < x ; ++ i )
const int inf = 0x7fffffff ;
const int maxn = 510000 ;
const int maxm = 510000 ;
const int maxv = 510000 + maxm ;
struct node {
node *lc , *rc ;
bool tag , Tag ;
int x , y , flag , mx[ 2 ] , mn[ 2 ] ;
node( ) {
lc = rc = NULL , tag = Tag = false ;
}
} kdt[ maxv ] ;
node *pt = kdt , *root ;
struct point {
int x , y ;
inline void oper( int _x , int _y ) {
x = _x , y = _y ;
}
bool operator < ( const point &a ) const {
return x < a.x || ( x == a.x && y < a.y ) ;
}
bool operator == ( const point &a ) const {
return x == a.x && y == a.y ;
}
bool operator != ( const point &a ) const {
return x != a.x || y != a.y ;
}
} p[ maxn + maxm ] , b[ maxn + maxm ] ;
int n , m , q[ maxm ][ 3 ] , cnt , N = 0 , a[ maxn ][ 2 ] ;
void Selectx( int l , int r , int k ) {
if ( l >= r ) return ;
int i = l , j = r , x = b[ ( l + r ) >> 1 ].x ;
do {
for ( ; b[ i ].x < x ; ++ i ) ;
for ( ; b[ j ].x > x ; -- j ) ;
if ( i <= j ) swap( b[ i ++ ] , b[ j -- ] ) ;
} while ( i <= j ) ;
if ( i < r && k >= i && k <= r ) Selectx( i , r , k ) ;
if ( j > l && k >= l && k <= j ) Selectx( l , j , k ) ;
}
void Selecty( int l , int r , int k ) {
if ( l >= r ) return ;
int i = l , j = r , y = b[ ( l + r ) >> 1 ].y ;
do {
for ( ; b[ i ].y < y ; ++ i ) ;
for ( ; b[ j ].y > y ; -- j ) ;
if ( i <= j ) swap( b[ i ++ ] , b[ j -- ] ) ;
} while ( i <= j ) ;
if ( i < r && k >= i && k <= r ) Selecty( i , r , k ) ;
if ( j > l && k >= l && k <= j ) Selecty( l , j , k ) ;
}
void build( int l , int r , bool flag , node* &t ) {
if ( l > r ) return ;
t = pt ++ ;
int mid = ( l + r ) >> 1 ;
if ( t -> flag = flag ) Selectx( l , r , mid ) ; else Selecty( l , r , mid ) ;
t -> x = b[ mid ].x , t -> y = b[ mid ].y ;
int _l = l , _r = r ;
if ( flag ) {
while ( _l < _r ) {
for ( ; b[ _l ].x <= t -> x && _l <= r ; ++ _l ) ;
for ( ; b[ _r ].x > t -> x && _r >= l ; -- _r ) ;
if ( _l < _r ) swap( b[ _l ++ ] , b[ _r -- ] ) ;
}
for ( _l = l ; b[ _l + 1 ].x <= t -> x && _l < r ; ++ _l ) ;
REP( i , l , ( _l - 1 ) ) if ( b[ i ].x == t -> x && b[ i ].y == t -> y ) {
swap( b[ i ] , b[ _l ] ) ; break ;
}
} else {
while ( _l < _r ) {
for ( ; b[ _l ].y <= t -> y && _l <= r ; ++ _l ) ;
for ( ; b[ _r ].y > t -> y && _r >= l ; -- _r ) ;
if ( _l < _r ) swap( b[ _l ++ ] , b[ _r -- ] ) ;
}
for ( _l = l ; b[ _l + 1 ].y <= t -> y && _l < r ; ++ _l ) ;
REP( i , l , ( _l - 1 ) ) if ( b[ i ].x == t -> x && b[ i ].y == t -> y ) {
swap( b[ i ] , b[ _l ] ) ; break ;
}
}
t -> mn[ 0 ] = t -> mn[ 1 ] = inf , t -> mx[ 0 ] = t -> mx[ 1 ] = - inf ;
REP( i , l , r ) {
t -> mn[ 0 ] = min( t -> mn[ 0 ] , b[ i ].x ) ;
t -> mn[ 1 ] = min( t -> mn[ 1 ] , b[ i ].y ) ;
t -> mx[ 0 ] = max( t -> mx[ 0 ] , b[ i ].x ) ;
t -> mx[ 1 ] = max( t -> mx[ 1 ] , b[ i ].y ) ;
}
build( l , _l - 1 , flag ^ true , t -> lc ) ;
build( _l + 1 , r , flag ^ true , t -> rc ) ;
}
void change( int x , int y , node *t ) {
t -> Tag = true ;
if ( t -> x == x && t -> y == y ) {
t -> tag = true ; return ;
}
if ( t -> flag ) {
if ( x <= t -> x ) change( x , y , t -> lc ) ; else change( x , y , t -> rc ) ;
} else {
if ( y <= t -> y ) change( x , y , t -> lc ) ; else change( x , y , t -> rc ) ;
}
}
int ans ;
void query( int x , int y , node *t ) {
if ( ! t ) return ;
if ( ! t -> Tag ) return ;
if ( t -> tag ) ans = min( ans , abs( x - t -> x ) + abs( y - t -> y ) ) ;
if ( ! ans ) return ;
int d = 0 ;
if ( x > t -> mx[ 0 ] ) d += x - t -> mx[ 0 ] ;
if ( x < t -> mn[ 0 ] ) d += t -> mn[ 0 ] - x ;
if ( y > t -> mx[ 1 ] ) d += y - t -> mx[ 1 ] ;
if ( y < t -> mn[ 1 ] ) d += t -> mn[ 1 ] - y ;
if ( d >= ans ) return ;
if ( t -> flag ) {
if ( x <= t -> x ) {
query( x , y , t -> lc ) ;
if ( t -> x + 1 - x < ans ) query( x , y , t -> rc ) ;
} else {
query( x , y , t -> rc ) ;
if ( x - t -> x < ans ) query( x , y , t -> lc ) ;
}
} else {
if ( y <= t -> y ) {
query( x , y , t -> lc ) ;
if ( t -> y + 1 - y < ans ) query( x , y , t -> rc ) ;
} else {
query( x , y , t -> rc ) ;
if ( y - t -> y < ans ) query( x , y , t -> lc ) ;
}
}
}
int ch ;
inline void getint( int &t ) {
for ( ch = getchar( ) ; ch < '0' || ch > '9' ; ch = getchar( ) ) ; t = ch - '0' ;
for ( ch = getchar( ) ; ch >= '0' && ch <= '9' ; ch = getchar( ) ) t = t * 10 + ch - '0' ;
}
int main( ) {
getint( n ) , getint( m ) ;
rep( i , n ) {
getint( a[ i ][ 0 ] ) , getint( a[ i ][ 1 ] ) ;
p[ i ].oper( a[ i ][ 0 ] , a[ i ][ 1 ] ) ;
}
cnt = n ;
rep( i , m ) {
getint( q[ i ][ 0 ] ) , getint( q[ i ][ 1 ] ) , getint( q[ i ][ 2 ] ) ;
if ( q[ i ][ 0 ] == 1 ) p[ ++ cnt ].oper( q[ i ][ 1 ] , q[ i ][ 2 ] ) ;
}
sort( p + 1 , p + cnt + 1 ) ;
rep( i , cnt ) if ( i == 1 || p[ i ] != p[ i - 1 ] ) b[ ++ N ] = p[ i ] ;
random_shuffle( b + 1 , b + N + 1 ) ;
build( 1 , N , true , root ) ;
rep( i , n ) {
change( a[ i ][ 0 ] , a[ i ][ 1 ] , root ) ;
}
rep( i , m ) if ( q[ i ][ 0 ] == 1 ) change( q[ i ][ 1 ] , q[ i ][ 2 ] , root ) ; else {
ans = inf ; query( q[ i ][ 1 ] , q[ i ][ 2 ] , root ) ;
printf( "%d\n" , ans ) ;
}
return 0 ;
}
网友评论