HDU 4189 Cybercrime Donut Investigation 线段树+思路

HDU 4189 Cybercrime Donut Investigation 线段树+思路

参考：.html

 题意：给一个有n个点的点集，有q个询问，每个询问询问一个点p，求与p曼哈顿距离最小的点，并输出曼哈顿距离的最小值。

分析：使得abs(qx - xi) + abs(qy - yi)最小，因为带了个绝对值，所以没法直接套用一些数据结构中查询最值的操作，一时间也没什么头绪。后来看到上面的博客，才明白可以分情况讨论，把绝对值去掉。

一共四种情况：

qx >= xi && qy >= yi

qx >= xi && qy <= yi

qx <= xi && qy >= yi

qx <= xi && qy <= yi

以第一种情况为例分析，其他三种情况分析方法相同。

当 qx > xi && qy > yi 时，直接去绝对值得到：qx - xi + qy - yi = ( qx + qy ) - ( xi +yi )，因为对于每个查询qx + qy相当于一个常数，所以若使qx - xi + qy - yi最小，则 (xi + yi) 最大即可。

于是就转换成了单点更新+区间查最值问题。

线段树离线处理：将点集和查询一块考虑，按上述四种情况分别对点排序，x为第一优先级，y为第二优先级。

将y坐标离散化。

对于每个询问，查询其所属的区间中的最大值。

PS1.其实不用搞四次的，不过这样比较好理解……

PS2.sort函数要仔细考虑一下，跟循环正着跑还是倒着跑有关，之前这里没考虑清楚，样例都跑不对。

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>#define LL long long int
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1using namespace std;const int MAXN = 100000 + 50100;
const LL INF = 1LL << 62;struct node
{LL x, y;int id;void readNode(){scanf( "%I64d%I64d", &x, &y );return;}
};bool cmp1( node a, node b )
{if ( a.x != b.x ) return a.x < b.x;if ( a.y != b.y ) return a.y < b.y;return a.id < b.id;
}bool cmp2( node a, node b )
{if ( a.x != b.x ) return b.x < a.x;if ( a.y != b.y ) return a.y < b.y;return b.id < a.id;
}bool cmp3( node a, node b )
{if ( a.x != b.x ) return b.x < a.x;if ( a.y != b.y ) return a.y < b.y;return a.id < b.id;
}bool cmp4( node a, node b )
{if ( a.x != b.x ) return a.x < b.x;if ( a.y != b.y ) return a.y < b.y;return b.id < a.id;
}int N, Q;
int all, cntY;
node D[MAXN];
LL maxi[ MAXN << 2 ];
LL ans[MAXN];
LL hashY[MAXN];void build( int l, int r, int rt )
{maxi[rt] = -INF;if ( l == r ) return;int m = ( l + r ) >> 1;build( lson );build( rson );return;
}void PushUp( int rt )
{maxi[rt] = max( maxi[rt << 1], maxi[rt << 1 | 1] );
}void update( LL val, int pos, int l, int r, int rt )
{if ( l == pos && r == pos ){maxi[rt] = max( maxi[rt], val );return;}int m = ( l + r ) >> 1;if ( pos <= m ) update( val, pos, lson );else update( val, pos, rson );PushUp( rt );return;
}LL query( int L, int R, int l, int r, int rt )
{if ( L <= l && r <= R ){return maxi[rt];}LL res = -INF;int m = ( l + r ) >> 1;if ( L <= m ) res = max( res, query( L, R, lson ) );if ( R > m  ) res = max( res, query( L, R, rson ) );return res;
}void init()
{for ( int i = 0; i < N; ++i ){D[i].readNode();D[i].id = -1;hashY[i] = D[i].y;}scanf( "%d", &Q );for ( int i = 0; i < Q; ++i ){D[ N + i ].readNode();D[ N + i ].id = i;hashY[ N + i ] = D[N + i].y;ans[i] = INF;}all = N + Q;sort( hashY, hashY + all );cntY = unique( hashY, hashY + all ) - hashY;return;
}int main()
{int cas = 0;while ( scanf( "%d", &N ), N != -1 ){init();build( 1, cntY, 1 );sort( D, D + all, cmp1 );for ( int i = 0; i < all; ++i ){int id = lower_bound( hashY, hashY + cntY, D[i].y ) - hashY;++id;if ( D[i].id == -1 ) update( D[i].x + D[i].y, id, 1, cntY, 1 );else{ans[ D[i].id ] = min( ans[ D[i].id ], D[i].x + D[i].y - query( 1, id, 1, cntY, 1 ) );}}build( 1, cntY, 1 );sort( D, D + all, cmp2 );for ( int i = all - 1; i >= 0; --i ){int id = lower_bound( hashY, hashY + cntY, D[i].y ) - hashY;++id;if ( D[i].id == -1 ) update( D[i].x - D[i].y, id, 1, cntY, 1 );else{ans[ D[i].id ] = min( ans[ D[i].id ], D[i].x - D[i].y - query( id, cntY, 1, cntY, 1 ) );}}build( 1, cntY, 1 );sort( D, D + all, cmp3 );for ( int i = 0; i < all; ++i ){int id = lower_bound( hashY, hashY + cntY, D[i].y ) - hashY;++id;if ( D[i].id == -1 ) update( D[i].y - D[i].x, id, 1, cntY, 1 );else{ans[ D[i].id ] = min( ans[ D[i].id ], D[i].y - D[i].x - query( 1, id, 1, cntY, 1 ) );}}build( 1, cntY, 1 );sort( D, D + all, cmp4 );for ( int i = all - 1; i >= 0; --i ){int id = lower_bound( hashY, hashY + cntY, D[i].y ) - hashY;++id;if ( D[i].id == -1 ) update( -D[i].x - D[i].y, id, 1, cntY, 1 );else{ans[ D[i].id ] = min( ans[ D[i].id ], -D[i].x - D[i].y - query( id, cntY, 1, cntY, 1 ) );}}if ( cas ) puts("");for ( int i = 0; i < Q; ++i )printf( "%I64dn", ans[i] );++cas;}return 0;
}

转载于:.html