P4169 [Violet]天使玩偶/SJY摆棋子

首先这题显然可以 CDQ，分四个方向分别跑就行了，拆出来的条件是一个三维偏序问题。

但是 $3 \times 10^5$ 的数据范围导致 CDQ 很容易被卡常啊。。（实际上也确实有很多被卡了）。

所以考虑可以用玄学 K-DTree 来维护。

具体来说，考虑从根开始向下行走，每走一个点就更新一下答案。每次查一下这个点到两边矩形的最小距离是否超过了当前的答案，如果是就不走了。

一个优化是，每次先进入距离最小的子树。

这样最坏是 $O(n^2)$ 的，但是随机数据跑得跟 $O(n\log n)$ 一样快。

cpp

#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "map"
#include "set"
#include "queue"
using namespace std;
#define MAXN 600006
//#define int long long
#define rep(i, a, b) for (int i = (a), i##end = (b); i <= i##end; ++i)
#define per(i, a, b) for (int i = (a), i##end = (b); i >= i##end; --i)
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define all(x) (x).begin() , (x).end()
#define mem( a ) memset( a , 0 , sizeof a )
#define min( a , b ) ( (a) < (b) ? (a) : (b) )
#define max( a , b ) ( (a) > (b) ? (a) : (b) )
typedef long long ll;

void rd( int& x ) {
    x = 0; char ch = ' ';
    while( ch > '9' || ch < '0' ) ch = getchar( );
    while( ch >= '0' && ch <= '9' ) x = 10 * x + ch - '0' , ch = getchar();
}

int n , m , rt = 1;

#define ratio 0.75
#define cont( x1 , y1 , x2 , y2 , X1 , Y1 , X2 , Y2 ) ( x1 <= X1 && y1 <= Y1 && x2 >= X2 && y2 >= Y2  )
#define out( x1 , y1 , x2 , y2 , X1 , Y1 , X2 , Y2 ) ( x1 > X2 || y1 > Y2 || x2 < X1 || y2 < Y1 )
#define abs( a ) ( (a) > 0 ? (a) : ( -(a) ) )

struct node {
    int d[2];
    void in( ) {
        rd( d[0] ) , rd( d[1] );
    }
} T[MAXN] , P[MAXN] , tmp ;

int cnt , rub[MAXN] , top;
int newnode( ) {
    if( top ) return rub[top --];
    return ++ cnt;
}

int D;
inline bool cmp( node a , node b ) {
    return a.d[D] < b.d[D];
}

int ch[MAXN][2] , lo[MAXN][2] , up[MAXN][2] , siz[MAXN];
inline void pu( int rt ) {
    int ls = ch[rt][0] , rs = ch[rt][1];
    rep( d , 0 , 1 ) {
        lo[rt][d] = up[rt][d] = T[rt].d[d];
        if( ls ) lo[rt][d] = min( lo[rt][d] , lo[ls][d] ) , up[rt][d] = max( up[rt][d] , up[ls][d] );
        if( rs ) lo[rt][d] = min( lo[rt][d] , lo[rs][d] ) , up[rt][d] = max( up[rt][d] , up[rs][d] );
    }
    siz[rt] = siz[ls] + 1 + siz[rs];
}
int build( int l , int r , int d ) {
    if( l > r ) return 0;
    int mid = l + r >> 1 , p = newnode( );
    D = d , nth_element( P + l , P + mid , P + r + 1 , cmp ) , T[p] = P[mid];
    ch[p][0] = build( l , mid - 1 , d ^ 1 ) , ch[p][1] = build( mid + 1 , r , d ^ 1 );
    pu( p );
    return p;
}

void pia( int u , int num ) {
    if( !u ) return;
    pia( ch[u][0] , num );
    P[num + siz[ch[u][0]] + 1] = T[u] , rub[++ top] = u;
    pia( ch[u][1] , num + siz[ch[u][0]] + 1 );
}

void mt( int& u , int d ) {
    if( siz[u] * ratio < siz[ch[u][0]] || siz[u] * ratio < siz[ch[u][1]] )
        pia( u , 0 ) , u = build( 1 , siz[u] , d );
}

void ins( int& u , node& x , int d ) {
//    cout << u << endl;
    if( !u ) { u = newnode( ) , ch[u][0] = ch[u][1] = 0 , T[u] = x , pu( u ); return; }
    if( x.d[d] <= T[u].d[d] ) ins( ch[u][0] , x , d ^ 1 );
    else ins( ch[u][1] , x , d ^ 1 );
    pu( u ); mt( u , d );
}

int dis( int x1 , int y1 , int x2 , int y2 ) {
    return abs( x2 - x1 ) + abs( y2 - y1 );
}
int calc( int u , node& t ) { // dis from t to matrix in node u
    if( cont( lo[u][0] , lo[u][1] , up[u][0] , up[u][1] , t.d[0] , t.d[1] , t.d[0] , t.d[1] ) ) return 0;
    rep( d , 0 , 1 )
        if( t.d[d] >= lo[u][d] && t.d[d] <= up[u][d] ) return min( abs( t.d[d ^ 1] - lo[u][d ^ 1] ) , abs( t.d[d ^ 1] - up[u][d ^ 1] ) );
    int x = t.d[0] , y = t.d[1];
    return min( min( dis( x , y , lo[u][0] , lo[u][1] ) , dis( x , y , lo[u][0] , up[u][1] ) ) , min( dis( x , y , up[u][0] , up[u][1] ) , dis( x , y , up[u][0] , lo[u][1] ) ) );
}

int ans;
void que( int u , node& x ) {
//    cout << u << endl;
    if( !u ) return;
    ans = min( ans , dis( x.d[0] , x.d[1] , T[u].d[0] , T[u].d[1] ) );
    int ls = 0x3f3f3f3f , rs = 0x3f3f3f3f;
    if( ch[u][0] ) ls = min( ls , calc( ch[u][0] , x ) );
    if( ch[u][1] ) rs = min( rs , calc( ch[u][1] , x ) );
    if( ls < ans && ls <= rs ) {
        que( ch[u][0] , x );
        if( rs < ans ) que( ch[u][1] , x );
    } else if( rs < ans && rs <= ls ) {
        que( ch[u][1] , x );
        if( ls < ans ) que( ch[u][0] , x );
    }
}

void solve() {
    cin >> n >> m;
    rep( i , 1 , n ) {
        P[i].in();
    }
    build( 1 , n , 0 );
    int op;
    rep( i , 1 , m ) {
        rd( op ); tmp.in( );
        if( op == 1 ) {
            ins( rt , tmp , 0 );
        } else {
            ans = 0x3f3f3f3f;
            que( rt , tmp );
            printf("%d\n",ans);
        }
    }
}

signed main() {
//    freopen("P4169_2.in","r",stdin);
//    freopen("fuckout","w",stdout);
//    int T;cin >> T;while( T-- ) solve();
    solve();
}