蒯了一遍模板发现好多机房神犇都切过这道题了
多年没刷题都跟不上节奏了 现在才会kdt
建树的方法挺鬼畜的 每次换一维选最中间的点切开再往两边建树
然后插入和二叉搜索树差不多
查询就是一路往下查 剪剪枝
复杂度特别鬼畜 主要是看剪枝
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 |
// <2648.cpp> - 12/27/16 19:14:13 // This file is created by XuYike's black technology automatically. // Copyright (C) 2015 ChangJun High School, Inc. // I don't know what this program is. #include <iostream> #include <vector> #include <algorithm> #include <cstring> #include <cstdio> #include <cmath> using namespace std; typedef long long lol; int gi(){ int res=0,fh=1;char ch=getchar(); while((ch>'9'||ch<'0')&&ch!='-')ch=getchar(); if(ch=='-')fh=-1,ch=getchar(); while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar(); return fh*res; } const int MAXN=1000010; const int INF=1e9; #define fi01() for(int i=0;i<=1;i++) bool K; struct T{ int a[2],mn[2],mx[2],l,r; T(int x=0,int y=0){a[0]=x;a[1]=y;l=r=0;} bool operator <(const T b) const{return a[K]<b.a[K];} }t[MAXN],S; int n,root; void update(int x){ fi01(){ if(t[x].l){ t[x].mn[i]=min(t[x].mn[i],t[t[x].l].mn[i]); t[x].mx[i]=max(t[x].mx[i],t[t[x].l].mx[i]); } if(t[x].r){ t[x].mn[i]=min(t[x].mn[i],t[t[x].r].mn[i]); t[x].mx[i]=max(t[x].mx[i],t[t[x].r].mx[i]); } } } int build(int l,int r,bool p){ K=p; int m=l+r>>1; nth_element(t+l,t+m,t+r+1); fi01()t[m].mn[i]=t[m].mx[i]=t[m].a[i]; if(l<m)t[m].l=build(l,m-1,p^1); if(r>m)t[m].r=build(m+1,r,p^1); update(m); return m; } int ans; inline int gd(T &b){return abs(S.a[0]-b.a[0])+abs(S.a[1]-b.a[1]);} inline int get(int k){ if(!k)return INF; int g=0; fi01()g+=max(0,t[k].mn[i]-S.a[i])+max(0,S.a[i]-t[k].mx[i]); return g; } void query(int k){ ans=min(ans,gd(t[k])); int dl=get(t[k].l),dr=get(t[k].r); if(dl<dr){ if(dl<ans)query(t[k].l); if(dr<ans)query(t[k].r); }else{ if(dr<ans)query(t[k].r); if(dl<ans)query(t[k].l); } } void insert(int k,bool p){ K=p; if(S<t[k]){ if(t[k].l)insert(t[k].l,p^1); else{ t[t[k].l=++n]=S; fi01()t[n].mn[i]=t[n].mx[i]=t[n].a[i]; } }else{ if(t[k].r)insert(t[k].r,p^1); else{ t[t[k].r=++n]=S; fi01()t[n].mn[i]=t[n].mx[i]=t[n].a[i]; } } update(k); } int main(){ n=gi();int m=gi(); for(int i=1;i<=n;i++)t[i].a[0]=gi(),t[i].a[1]=gi(); root=build(1,n,0); while(m--){ int op=gi(),x=gi(),y=gi(); S=T(x,y); if(op==1)insert(root,0); else{ ans=INF; query(root); printf("%d\n",ans); } } return 0; } |
泥又刷火题
这题我都没做过