HDU 4189 Cybercrime Donut Investigation 线段树+思路

参考：http://www.cnblogs.com/slon/archive/2012/03/30/2426104.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 | 1

using 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( "%I64d
", ans[i] );
        ++cas;
    }
    return 0;
}