BZOJ 2648 SJY摆箱子

kdtree模板题

我判是否查询时用mid来判没有存极值，然后貌似被卡常了？

hzwer的代码在我本地的随机数据中跑得没我快...难道bzoj上的数据有构造的？

//By Richard
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <ctime>
#define rep(x,y,z) for (int x=(y);(x)<=(z);(x)++)
#define per(x,y,z) for (int x=(y);(x)>=(z);(x)--)
#define log2(x) (31-__builtin_clz(x))
#define mod (int)(1e9+7)
#define inf 0x3f3f3f3f
#define cls(x) memset(x,0,sizeof(x))
#ifdef DEBUG
#define debugdo(X) X
#define debugndo(X)
#define debugout(X) cout<<(#X)<<"="<<(X)<<endl
#else
#define debugdo(X)
#define debugndo(X) X
#define debugout(X)
#endif // debug
#ifdef ONLINE_JUDGE
#define debugdo(X)
#define debugndo(X) X
#define debugout(X)
#endif
#define putarray(x,n) rep(iiii,1,n) printf("%d ",x[iiii])
#define mp make_pair
using namespace std;
typedef pair<int,int> pairs;
typedef long long LL;
/////////////////////read3.0////////////////////////////////////
template <typename T>
inline void read(T &x){char ch;x=0;bool flag=false;ch=getchar();while (ch>'9'||ch<'0') {ch=getchar();if (ch=='-') flag=true;}while ((ch<='9'&&ch>='0')){x=x*10+ch-'0';ch=getchar();}if (flag) x*=-1;}
template <typename T>
inline void read(T &x,T &y){read(x);read(y);}
/////////////////variables&functions////////////////////
const int maxn=1111111;
int n,doing,m,ans;
bool now;
struct POINT
{
    int x,y;
}point[maxn];
struct Node
{
    Node *l,*r;
    int id;
    inline bool operator<(const Node &other)const
    {
        if (now) return point[id].x<point[other.id].x;
        else return point[id].y<point[other.id].y;
    }
}node[maxn];
struct kd_tree
{
    Node *root;
    // Node node[maxn];
    inline void init(const int &vv)
    {
        rep(i,1,vv) node[i].id=i;
    }
    Node *build(const int &l,const int &r,const bool &d)
    {
        if (l==r) return node+l;
        else if (l>r) return 0;
        now=d;
        int mid=(l+r)>>1;
        nth_element(node+l,node+mid,node+r+1);
        node[mid].l=build(l,mid-1,d^1);
        node[mid].r=build(mid+1,r,d^1);
        return &node[mid];
    } 
    inline void insert(const int &x)
    {
        // doing=x;
        node[x].id=x;
        Node *nowp=root;
        bool now=1;
        while (1)
        {
            if (now)
            {
                if (point[x].x<point[nowp->id].x)
                {
                    if (nowp->l) nowp=nowp->l;
                    else 
                    {
                        nowp->l=&node[x];
                        break;
                    }
                }
                else 
                {
                    if (nowp->r) nowp=nowp->r;
                    else
                    {
                        nowp->r=&node[x];
                        break;
                    }
                }
            }
            else
            {
                if (point[x].y<point[nowp->id].y) 
                {
                    if (nowp->l) nowp=nowp->l;
                    else 
                    {
                        nowp->l=&node[x];
                        break;
                    }
                }
                else 
                {
                    if (nowp->r) nowp=nowp->r;
                    else
                    {
                        nowp->r=&node[x];
                        break;
                    }
                }
            }
            now^=1;
        }
    }
    inline int dis(const int &x)
    {
        return abs(point[x].x-point[doing].x)+abs(point[x].y-point[doing].y);
    }
    void querycore(const Node *x,const bool &d)
    {
        // now=d;
        ans=min(ans,dis(x->id));
        if (d)
        {
            if (point[x->id].x>point[doing].x)
            {
                if (x->l) querycore(x->l,d^1);
                if (point[x->id].x-point[doing].x<ans&&x->r) querycore(x->r,d^1);
            }
            else
            {
                if (x->r) querycore(x->r,d^1);
                if (point[doing].x-point[x->id].x<ans&&x->l) querycore(x->l,d^1);
            }
        }
        else
        {
            if (point[x->id].y>point[doing].y)
            {
                if (x->l) querycore(x->l,d^1);
                if (point[x->id].y-point[doing].y<ans&&x->r) querycore(x->r,d^1);
            }
            else
            {
                if (x->r) querycore(x->r,d^1);
                if (point[doing].y-point[x->id].y<ans&&x->l) querycore(x->l,d^1);
            }
        }
    }
    inline int query(const int &x)
    {
        ans=inf;
        doing=x;
        querycore(root,1);
        return ans;
    }
}kdtree;
int main()
{
    read(n,m);
    kdtree.init(n+m);
    rep(i,1,n) read(point[i].x,point[i].y);
    kdtree.root=kdtree.build(1,n,1);
    int tt;
    rep(i,n+1,n+m)
    {
        read(tt);
        read(point[i].x,point[i].y);
        if (tt==2) printf("%d\n",kdtree.query(i));
        else kdtree.insert(i);

}
return 0;
}