2648: SJY摆棋子

https://www.lydsy.com/JudgeOnline/problem.php?id=2648

分析：　　　

　　k-d tree 模板题。

代码：

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long LL;

 inline int read() {

     int x=,f=;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-;

     for (;isdigit(ch);ch=getchar())x=x*+ch-'';return x*f;

 }

 const int N = ;

 const int DIM = ;

 const int INF = 1e9;

 #define lc T[rt].ch[0]

 #define rc T[rt].ch[1]

 struct Point {

     int x[];

     Point() {x[] = ,x[] = ;}

     Point(int a,int b) {x[] = a,x[] = b;}

 }P[N];

 struct KD_Tree {

     int ch[],mn[],mx[];

     Point p;

 }T[N<<];

 int Cur,CntNode,Ans,Root;

 inline bool cmp(Point a,Point b) {

     return a.x[Cur] < b.x[Cur];

 }

 inline void pushup(int rt) {

     for (int i=; i<DIM; ++i) {

         if (lc) T[rt].mn[i] = min(T[rt].mn[i],T[lc].mn[i]), T[rt].mx[i] = max(T[rt].mx[i],T[lc].mx[i]);

         if (rc) T[rt].mn[i] = min(T[rt].mn[i],T[rc].mn[i]), T[rt].mx[i] = max(T[rt].mx[i],T[rc].mx[i]); // -- rc - lc

     }

 }

 inline void NewNode(int rt,Point p) {

     T[rt].p = p;

     T[rt].mn[] = T[rt].mx[] = p.x[];

     T[rt].mn[] = T[rt].mx[] = p.x[];

 }

 int build(int l,int r,int cd) { // cd -- cur dimensions

     if (l > r) return ;

     int m = (l + r) >> ,rt = m;

     Cur = cd; nth_element(P+l, P+m, P+r+, cmp);

     NewNode(rt,P[m]);

     lc = build(l, m-, cd^);

     rc = build(m+, r, cd^);

     pushup(rt);

     return rt;

 }

 void Insert(Point p,int &rt,int cd) {

     if (!rt) {

         NewNode(rt = ++CntNode,p);return ;

     }

     if (p.x[cd] <= T[rt].p.x[cd]) Insert(p, lc, cd^);

     else Insert(p, rc, cd^);

     pushup(rt);

 }

 inline int dist(Point a,KD_Tree b) {

     int dis = ;

     if (a.x[] < b.mn[]) dis += b.mn[] - a.x[];

     if (a.x[] > b.mx[]) dis += a.x[] - b.mx[];

     if (a.x[] < b.mn[]) dis += b.mn[] - a.x[];

     if (a.x[] > b.mx[]) dis += a.x[] - b.mx[];

     return dis;

 }

 inline int dis(Point a,Point b) {

     return abs(a.x[] - b.x[]) + abs(a.x[] - b.x[]);

 }

 void query(Point p,int rt) {

     Ans = min(Ans,dis(p,T[rt].p)); // -- !!

     int dl = lc ? dist(p,T[lc]) : INF;

     int dr = rc ? dist(p,T[rc]) : INF;

     if (dl < dr) {

         if (dl < Ans) query(p,lc);

         if (dr < Ans) query(p,rc);

     }

     else {

         if (dr < Ans) query(p,rc);

         if (dl < Ans) query(p,lc);

     }

 }

 int main() {

     int n = read(),m = read();

     CntNode = n; // --- !!!

     for (int i=; i<=n; ++i)

         P[i].x[] = read(),P[i].x[] = read();

     Root = build(,n,);

     while (m--) {

         int opt = read(),x = read(),y = read();

         if (opt == ) Insert(Point(x,y),Root,);

         else {

             Ans = INF;

             query(Point(x,y),Root);

             printf("%d\n",Ans);

         }

     }

     return ;

 }

luogu上需要拍扁重构，否则会T，而bzoj上拍扁重构却不如不拍扁重构跑得快

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long LL;

 inline int read() {

     int x=,f=;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-;

     for (;isdigit(ch);ch=getchar())x=x*+ch-'';return x*f;

 }

 const int N = ;

 const int DIM = ;

 const int INF = 1e9;

 #define alpha 0.75

 #define lc T[rt].ch[0]

 #define rc T[rt].ch[1]

 struct Point {

     int x[];

     Point() {x[] = ,x[] = ;}

     Point(int a,int b) {x[] = a,x[] = b;}

 }P[N<<];

 struct KD_Tree {

     int ch[],mn[],mx[],sz;

     Point p;

 }T[N<<];

 int sk[N],Top,Cur,CntNode,Ans,Root;

 inline bool cmp(Point a,Point b) {

     return a.x[Cur] < b.x[Cur];

 }

 inline void pushup(int rt) {

     T[rt].sz = T[lc].sz + T[rc].sz + ; //-- +1！！！

     for (int i=; i<DIM; ++i) {

         if (lc) T[rt].mn[i] = min(T[rt].mn[i],T[lc].mn[i]), T[rt].mx[i] = max(T[rt].mx[i],T[lc].mx[i]);

         if (rc) T[rt].mn[i] = min(T[rt].mn[i],T[rc].mn[i]), T[rt].mx[i] = max(T[rt].mx[i],T[rc].mx[i]);

     }

 }

 inline void NewNode(int &rt,Point p) {

     rt = Top ? sk[Top--] : ++CntNode;

     T[rt].p = p;

     T[rt].sz = ; // --！！！

     T[rt].mn[] = T[rt].mx[] = p.x[];

     T[rt].mn[] = T[rt].mx[] = p.x[];

 }

 int build(int l,int r,int cd) { // cd -- cur dimensions

     if (l > r) return ;

     int m = (l + r) >> ,rt;

     Cur = cd; nth_element(P+l, P+m, P+r+, cmp);

     NewNode(rt,P[m]);

     lc = build(l, m-, cd^);

     rc = build(m+, r, cd^);

     pushup(rt);

     return rt;

 }

 void dfs(int rt,int num) {

     if (lc) dfs(lc, num);

     P[num+T[lc].sz+] = T[rt].p, sk[++Top] = rt;

     if (rc) dfs(rc, num+T[lc].sz+);

 }

 inline void check(int &rt,int cd) {

     if (alpha * T[rt].sz < T[lc].sz || alpha * T[rt].sz < T[rc].sz) {

         dfs(rt, );

         rt = build(, T[rt].sz, cd);

     }

 }

 void Insert(Point p,int &rt,int cd) {

     if (!rt) {

         NewNode(rt,p);return ;

     }

     if (p.x[cd] <= T[rt].p.x[cd]) Insert(p, lc, cd^);

     else Insert(p, rc, cd^);

     pushup(rt);check(rt,cd);

 }

 inline int dist(Point a,KD_Tree b) {

     int dis = ;

     if (a.x[] < b.mn[]) dis += b.mn[] - a.x[];

     if (a.x[] > b.mx[]) dis += a.x[] - b.mx[];

     if (a.x[] < b.mn[]) dis += b.mn[] - a.x[];

     if (a.x[] > b.mx[]) dis += a.x[] - b.mx[];

     return dis;

 }

 inline int dis(Point a,Point b) {

     return abs(a.x[] - b.x[]) + abs(a.x[] - b.x[]);

 }

 void query(Point p,int rt) {

     Ans = min(Ans,dis(p,T[rt].p)); // -- !!

     int dl = lc ? dist(p,T[lc]) : INF;

     int dr = rc ? dist(p,T[rc]) : INF;

     if (dl < dr) {

         if (dl < Ans) query(p,lc);

         if (dr < Ans) query(p,rc);

     }

     else {

         if (dr < Ans) query(p,rc);

         if (dl < Ans) query(p,lc);

     }

 }

 int main() {

     int n = read(),m = read();

     for (int i=; i<=n; ++i)

         P[i].x[] = read(),P[i].x[] = read();

     Root = build(,n,);

     while (m--) {

         int opt = read(),x = read(),y = read();

         if (opt == ) Insert(Point(x,y),Root,);

         else {

             Ans = INF;

             query(Point(x,y),Root);

             printf("%d\n",Ans);

         }

     }

     return ;

 }