menu ZigZagK的博客
account_circle

正在努力加载中QAQ

[KDT]BZOJ2648【SJY摆棋子】题解
apps BZOJ
local_offer 查看标签
comment 0 条评论

题目概述

维护一个点集,有两种操作:1.加入一个点。2.询问 $(x,y)$ 到点集中曼哈顿距离最小值。

解题报告

KDT入门可以看这里

KDT玄学玩意……我没写重构就过了,写了重构反而TLE了……(反正查距离最小值复杂度本来就不对)

示例程序

#include<cstdio>
#include<cctype>
#include<algorithm>
using namespace std;
const int maxn=1000000;
 
int n,m,D,ro,son[maxn+5][2],MN[maxn+5][2],MX[maxn+5][2],ans;
struct Point {int x[2];inline bool operator < (const Point &a) const {return x[D]<a.x[D];}} a[maxn+5];
 
#define Eoln(x) ((x)==10||(x)==13||(x)==EOF)
inline char readc(){
    static char buf[100000],*l=buf,*r=buf;
    return l==r&&(r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++;
}
template<typename T> inline int readi(T &x){
    T tot=0;char ch=readc(),lst='+';
    while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();}
    while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc();
    return lst=='-'?x=-tot:x=tot,Eoln(ch);
}
inline void Pushup(int p){
    for (int i=0;i<2;i++) MN[p][i]=MX[p][i]=a[p].x[i];
    for (int j=0;j<2;j++)
        for (int i=0;son[p][j]&&i<2;i++)
            MN[p][i]=min(MN[p][i],MN[son[p][j]][i]),MX[p][i]=max(MX[p][i],MX[son[p][j]][i]);
}
int Build(int L,int R,int d=0){
    int m=L+(R-L>>1);D=d;nth_element(a+L,a+m,a+R+1);son[m][0]=son[m][1]=0;
    if (L<m) son[m][0]=Build(L,m-1,d^1);if (m<R) son[m][1]=Build(m+1,R,d^1);Pushup(m);return m;
}
void Insert(int &p,int d=0) {if (!p) return Pushup(p=n);D=d;Insert(son[p][a[p]<a[n]],d^1);Pushup(p);}
#define mindis(p,x,y) (max(MN[p][0]-(x),0)+max((x)-MX[p][0],0)+max(MN[p][1]-(y),0)+max((y)-MX[p][1],0))
inline int absi(int x) {return x<0?-x:x;}
void Ask(int p,int x,int y){
    if (!p) return;ans=min(ans,absi(a[p].x[0]-x)+absi(a[p].x[1]-y));int dis[2]={ans,ans};
    for (int i=0;i<2;i++) if (son[p][i]) dis[i]=mindis(son[p][i],x,y);int d=dis[0]>dis[1];
    if (dis[d]<ans) Ask(son[p][d],x,y);d^=1;if (dis[d]<ans) Ask(son[p][d],x,y);
}
int main(){
    readi(n);readi(m);for (int i=1;i<=n;i++) readi(a[i].x[0]),readi(a[i].x[1]);ro=Build(1,n);
    for (int i=1;i<=m;i++){
        int tp,x,y;readi(tp);readi(x);readi(y);
        if (tp==2) ans=2e9,Ask(ro,x,y),printf("%d\n",ans);
        else n++,a[n].x[0]=x,a[n].x[1]=y,Insert(ro);
    }return 0;
}
版权声明:本博客所有文章除特别声明外,均采用 CC BY 4.0 CN协议 许可协议。转载请注明出处!
名称不能为空
email
邮箱不能为空,请填写正确格式
link
网址请用http://或https://开头
message
评论不能为空
资瓷Markdown和LaTeX数学公式
sentiment_very_satisfied
keyboard_arrow_up