2648: SJY摆棋子

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

分析：　　　

　　k-d tree 模板题。

代码：

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 typedef long long LL;
  4  
  5 inline int read() {
  6     int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
  7     for (;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f;
  8 }
  9 
 10 const int N = 500010;
 11 const int DIM = 2;
 12 const int INF = 1e9;
 13  
 14 #define lc T[rt].ch[0]
 15 #define rc T[rt].ch[1]
 16  
 17 struct Point {
 18     int x[2];
 19     Point() {x[0] = 0,x[1] = 0;}
 20     Point(int a,int b) {x[0] = a,x[1] = b;}
 21 }P[N];
 22 struct KD_Tree {
 23     int ch[2],mn[2],mx[2];
 24     Point p;
 25 }T[N<<1];
 26 int Cur,CntNode,Ans,Root;
 27  
 28 inline bool cmp(Point a,Point b) {
 29     return a.x[Cur] < b.x[Cur];
 30 }
 31 inline void pushup(int rt) {
 32     for (int i=0; i<DIM; ++i) {
 33         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]);
 34         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
 35     }
 36 }
 37 inline void NewNode(int rt,Point p) {
 38     T[rt].p = p;
 39     T[rt].mn[0] = T[rt].mx[0] = p.x[0];
 40     T[rt].mn[1] = T[rt].mx[1] = p.x[1];
 41 }
 42 int build(int l,int r,int cd) { // cd -- cur dimensions
 43     if (l > r) return 0;
 44     int m = (l + r) >> 1,rt = m;
 45     Cur = cd; nth_element(P+l, P+m, P+r+1, cmp);
 46     NewNode(rt,P[m]);
 47     lc = build(l, m-1, cd^1);
 48     rc = build(m+1, r, cd^1);
 49     pushup(rt);
 50     return rt;
 51 }
 52 void Insert(Point p,int &rt,int cd) {
 53     if (!rt) {
 54         NewNode(rt = ++CntNode,p);return ;
 55     }
 56     if (p.x[cd] <= T[rt].p.x[cd]) Insert(p, lc, cd^1);
 57     else Insert(p, rc, cd^1);
 58     pushup(rt);
 59 }
 60 inline int dist(Point a,KD_Tree b) {
 61     int dis = 0;
 62     if (a.x[0] < b.mn[0]) dis += b.mn[0] - a.x[0];
 63     if (a.x[0] > b.mx[0]) dis += a.x[0] - b.mx[0];
 64     if (a.x[1] < b.mn[1]) dis += b.mn[1] - a.x[1];
 65     if (a.x[1] > b.mx[1]) dis += a.x[1] - b.mx[1];
 66     return dis;
 67 }
 68 inline int dis(Point a,Point b) {
 69     return abs(a.x[0] - b.x[0]) + abs(a.x[1] - b.x[1]);
 70 }
 71 void query(Point p,int rt) {
 72     Ans = min(Ans,dis(p,T[rt].p)); // -- !!
 73     int dl = lc ? dist(p,T[lc]) : INF;
 74     int dr = rc ? dist(p,T[rc]) : INF;
 75     if (dl < dr) {
 76         if (dl < Ans) query(p,lc);
 77         if (dr < Ans) query(p,rc);
 78     }
 79     else {
 80         if (dr < Ans) query(p,rc);
 81         if (dl < Ans) query(p,lc);
 82     }
 83 }
 84 int main() {
 85     int n = read(),m = read();
 86     CntNode = n; // --- !!!
 87     for (int i=1; i<=n; ++i) 
 88         P[i].x[0] = read(),P[i].x[1] = read();
 89     Root = build(1,n,1);
 90     while (m--) {
 91         int opt = read(),x = read(),y = read();
 92         if (opt == 1) Insert(Point(x,y),Root,1);
 93         else {
 94             Ans = INF;
 95             query(Point(x,y),Root);
 96             printf("%d
",Ans);
 97         }
 98     }
 99     return 0;
100 }

View Code

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

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 typedef long long LL;
  4  
  5 inline int read() {
  6     int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
  7     for (;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f;
  8 }
  9 
 10 const int N = 500010;
 11 const int DIM = 2;
 12 const int INF = 1e9;
 13  
 14 #define alpha 0.75
 15 #define lc T[rt].ch[0]
 16 #define rc T[rt].ch[1]
 17  
 18 struct Point {
 19     int x[2];
 20     Point() {x[0] = 0,x[1] = 0;}
 21     Point(int a,int b) {x[0] = a,x[1] = b;}
 22 }P[N<<1];
 23 struct KD_Tree {
 24     int ch[2],mn[2],mx[2],sz;
 25     Point p;
 26 }T[N<<1];
 27 int sk[N],Top,Cur,CntNode,Ans,Root;
 28  
 29 inline bool cmp(Point a,Point b) {
 30     return a.x[Cur] < b.x[Cur];
 31 }
 32 inline void pushup(int rt) {
 33     T[rt].sz = T[lc].sz + T[rc].sz + 1; //-- +1！！！ 
 34     for (int i=0; i<DIM; ++i) {
 35         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]);
 36         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]);
 37     }
 38 }
 39 inline void NewNode(int &rt,Point p) {
 40     rt = Top ? sk[Top--] : ++CntNode;
 41     T[rt].p = p;
 42     T[rt].sz = 1; // --！！！ 
 43     T[rt].mn[0] = T[rt].mx[0] = p.x[0];
 44     T[rt].mn[1] = T[rt].mx[1] = p.x[1];
 45 }
 46 int build(int l,int r,int cd) { // cd -- cur dimensions
 47     if (l > r) return 0;
 48     int m = (l + r) >> 1,rt;
 49     Cur = cd; nth_element(P+l, P+m, P+r+1, cmp);
 50     NewNode(rt,P[m]);
 51     lc = build(l, m-1, cd^1);
 52     rc = build(m+1, r, cd^1);
 53     pushup(rt);
 54     return rt;
 55 }
 56 void dfs(int rt,int num) {
 57     if (lc) dfs(lc, num);
 58     P[num+T[lc].sz+1] = T[rt].p, sk[++Top] = rt;
 59     if (rc) dfs(rc, num+T[lc].sz+1);
 60 } 
 61 inline void check(int &rt,int cd) {
 62     if (alpha * T[rt].sz < T[lc].sz || alpha * T[rt].sz < T[rc].sz) {
 63         dfs(rt, 0);
 64         rt = build(1, T[rt].sz, cd);
 65     }
 66 }
 67 void Insert(Point p,int &rt,int cd) {
 68     if (!rt) {
 69         NewNode(rt,p);return ;
 70     }
 71     if (p.x[cd] <= T[rt].p.x[cd]) Insert(p, lc, cd^1);
 72     else Insert(p, rc, cd^1);
 73     pushup(rt);check(rt,cd);
 74 }
 75 inline int dist(Point a,KD_Tree b) {
 76     int dis = 0;
 77     if (a.x[0] < b.mn[0]) dis += b.mn[0] - a.x[0];
 78     if (a.x[0] > b.mx[0]) dis += a.x[0] - b.mx[0];
 79     if (a.x[1] < b.mn[1]) dis += b.mn[1] - a.x[1];
 80     if (a.x[1] > b.mx[1]) dis += a.x[1] - b.mx[1];
 81     return dis;
 82 }
 83 inline int dis(Point a,Point b) {
 84     return abs(a.x[0] - b.x[0]) + abs(a.x[1] - b.x[1]);
 85 }
 86 void query(Point p,int rt) {
 87     Ans = min(Ans,dis(p,T[rt].p)); // -- !!
 88     int dl = lc ? dist(p,T[lc]) : INF;
 89     int dr = rc ? dist(p,T[rc]) : INF;
 90     if (dl < dr) {
 91         if (dl < Ans) query(p,lc);
 92         if (dr < Ans) query(p,rc);
 93     }
 94     else {
 95         if (dr < Ans) query(p,rc);
 96         if (dl < Ans) query(p,lc);
 97     }
 98 }
 99 int main() {
100     int n = read(),m = read();
101     for (int i=1; i<=n; ++i) 
102         P[i].x[0] = read(),P[i].x[1] = read();
103     Root = build(1,n,1);
104     while (m--) {
105         int opt = read(),x = read(),y = read();
106         if (opt == 1) Insert(Point(x,y),Root,1);
107         else {
108             Ans = INF;
109             query(Point(x,y),Root);
110             printf("%d
",Ans);
111         }
112     }
113     return 0;
114 }

View Code