bzoj2648 sjy摆棋子（kd-ag凯发k8国际
发布时间：2023/12/18
编程问答
16
豆豆
ag凯发k8国际
收集整理的这篇文章主要介绍了
bzoj2648 sjy摆棋子（kd-tree）
小编觉得挺不错的,现在分享给大家,帮大家做个参考.
板子题。
#include
#include
#include
#include
#include
#include
using namespace std;
#define ll long long
#define n 1000010
#define inf 2000000000
char getc(){char c=getchar();while ((c<'a'||c>'z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}
int gcd(int n,int m){return m==0?n:gcd(m,n%m);}
int read()
{int x=0,f=1;char c=getchar();while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}while (c>='0'&&c<='9') x=(x<<1) (x<<3) (c^48),c=getchar();return x*f;
}
int n,m,root,cnt,c,ans;
struct point
{int d[2],tag;bool operator <(const point&a) const{return d[c]<a.d[c];}
}a[n];
struct kdtree{int ch[2],a[2][2],tag;point p;
}tree[n];
struct data{int op;point p;
}q[n];
inline int dis(point u,point v){return abs(u.d[0]-v.d[0]) abs(u.d[1]-v.d[1]);}
inline void chkmin(int &x,int y){x=min(x,y);}
inline void chkmax(int &x,int y){x=max(x,y);}
inline bool isin(point x,int a[2][2]){return a[0][0]<=x.d[0]&&a[0][1]>=x.d[0]&&a[1][0]<=x.d[1]&&a[1][1]>=x.d[1];}
inline int max(int x,int y,int z){return max(max(x,y),z);}
inline int guess(point x,int a[2][2]){return max(0,a[0][0]-x.d[0],x.d[0]-a[0][1]) max(0,a[1][0]-x.d[1],x.d[1]-a[1][1]);}
void build(int &k,int l,int r,int op)
{if (l>r) return;k= cnt;c=op;int mid=l r>>1;nth_element(a l,a mid,a r 1);tree[k].p=a[mid],tree[k].tag=a[mid].tag,tree[k].a[0][0]=tree[k].a[0][1]=a[mid].d[0],tree[k].a[1][0]=tree[k].a[1][1]=a[mid].d[1];for (int i=l;i<=r;i )chkmin(tree[k].a[0][0],a[i].d[0]),chkmax(tree[k].a[0][1],a[i].d[0]),chkmin(tree[k].a[1][0],a[i].d[1]),chkmax(tree[k].a[1][1],a[i].d[1]);build(tree[k].ch[0],l,mid-1,op^1);build(tree[k].ch[1],mid 1,r,op^1);
}
void ins(int k,point x)
{if (!k) return;if (tree[k].p.d[0]==x.d[0]&&tree[k].p.d[1]==x.d[1]) {tree[k].tag=1;return;}if (isin(x,tree[tree[k].ch[0]].a)) ins(tree[k].ch[0],x);if (isin(x,tree[tree[k].ch[1]].a)) ins(tree[k].ch[1],x);
}
void query(int k,point x)
{if (!k) return;if (tree[k].tag) chkmin(ans,dis(x,tree[k].p));int p=tree[k].ch[0],q=tree[k].ch[1],u=guess(x,tree[p].a),v=guess(x,tree[q].a);if (v<u) swap(p,q),swap(u,v);if (u<ans) query(p,x);if (v<ans) query(q,x);
}
int main()
{
#ifndef online_judgefreopen("bzoj2648.in","r",stdin);freopen("bzoj2648.out","w",stdout);const char ll[]="%i64d\n";
#elseconst char ll[]="%lld\n";
#endifn=read(),m=read();for (int i=1;i<=n;i ) a[i].d[0]=read(),a[i].d[1]=read(),a[i].tag=1;for (int i=1;i<=m;i ){q[i].op=read(),q[i].p.d[0]=read(),q[i].p.d[1]=read();if (q[i].op==1) a[ n]=q[i].p;}build(root,1,n,0);for (int i=1;i<=m;i )if (q[i].op==1) ins(root,q[i].p);else ans=inf,query(root,q[i].p),printf("%d\n",ans);return 0;
}
转载于:https://www.cnblogs.com/gloid/p/10159247.html
总结
以上是ag凯发k8国际为你收集整理的bzoj2648 sjy摆棋子（kd-tree）的全部内容，希望文章能够帮你解决所遇到的问题。
如果觉得ag凯发k8国际网站内容还不错，欢迎将ag凯发k8国际推荐给好友。
