求离 \((x,y)\) 最近点的距离 距离的定义是 \(|x1-x2|+|y1-y2|\)
直接cdq 4次 考虑左上右上左下右下就可以了…略微卡常数…
#include <bits/stdc++.h>
#define ls(x) ch[x][0]
#define rs(x) ch[x][1]
#define rep(i , j , k) for(int i = j ; i <= k ; i ++)
#define Rep(i , j , k) for(int i = j ; i >= k ; i --)
using namespace std ;
using ll = long long ;
using pii = pair <int , int> ;
using vii = vector <int> ;
#define int long long
auto ot = [&]() { cerr << "ATS TXDY" << '\n' ; int ATS_nantf_txdy = true ; } ;
auto _ios = [&]() { ios :: sync_with_stdio(false) ; cin.tie(nullptr) ; cout.tie(nullptr) ; } ;
namespace stO_ATS_Orz {
template < class T > void cmax(T & x , T y) { if(x < y) x = y ; }
template < class T > void cmin(T & x , T y) { if(x > y) x = y ; }
template < class T > void abs(T x) { if(x < 0) x = -x ; }
int n , q , opt , x , y , len ;
const int N = 1e7 + 10 ;
const int INF = 2e7 + 10 ;
struct Node {
int x , y , type , id , ans ;
} a[N] , b[N] , tem[N] ;
struct BIT {
int c[N] ;
int low(int x) { return x & -x ; }
void upd(int x , int y) {
for( ; x <= len ; x += low(x)) cmax(c[x] , y) ;
}
int qry(int x) {
int ans = 0 ;
for( ; x ; x ^= low(x)) cmax(ans , c[x]) ;
return ans ? ans : -INF ;
}
void clear(int x) {
for( ; c[x] ; x += low(x)) c[x] = 0 ;
}
} t ;
void cdq(int l , int r) {
if(l == r) { return ; }
int mid = l + r >> 1 ;
cdq(l , mid) ; cdq(mid + 1 , r) ;
int t1 = l , t2 = mid + 1 , k = l ;
while(t2 <= r) {
while(t1 <= mid && b[t1].x <= b[t2].x){
if(b[t1].type == 1) t.upd(b[t1].y , b[t1].x + b[t1].y) ;
tem[k ++] = b[t1 ++] ;
}
if(b[t2].type == 2) cmin(a[b[t2].id].ans , b[t2].x + b[t2].y - t.qry(b[t2].y)) ;
tem[k ++] = b[t2 ++] ;
}
for(int i = l ; i <= t1 - 1 ; i ++)
if(b[i].type == 1) t.clear(b[i].y) ;
while(t1 <= mid) tem[k ++] = b[t1 ++] ;
for(int i = l ; i <= r ; i ++) b[i] = tem[i] ;
}
void solve(int rx , int ry) {
for(int i = 1 ; i <= n + q ; i ++) {
b[i] = a[i] ;
if(rx) b[i].x = len - b[i].x ;
if(ry) b[i].y = len - b[i].y ;
}
cdq(1 , n + q) ;
}
void main() {
cin >> n >> q ;
for(int i = 1 ; i <= n ; i ++) {
int x , y ; cin >> x >> y ; ++ x ; ++ y ;
a[i] = { x , y , 1 , i } ;
cmax(len , max(x , y)) ;
}
for(int i = n + 1 ; i <= n + q ; i ++) {
int opt , x , y ; cin >> opt >> x >> y ; ++ x ; ++ y ;
a[i] = { x , y , opt , i , INF } ;
cmax(len , max(x , y)) ;
}
++ len ;
solve(0 , 0) ; solve(0 , 1) ; solve(1 , 0) ; solve(1 , 1) ;
for(int i = n + 1 ; i <= n + q ; i ++)
if(a[i].type == 2) cout << a[i].ans << '\n' ;
}
}
signed main() {
_ios() ; ot() ;
return stO_ATS_Orz :: main() , 0 ;
}