[Violet]天使玩偶/SJY摆棋子 [cdq分治]

求离 \((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 ;

}
巴特西

[Violet]天使玩偶/SJY摆棋子 [cdq分治]

最新文章

热门文章
