bzoj 2648: SJY摆棋子 KDtree + 替罪羊式重构

KDtree真的很妙啊，真的是又好写，作用还多，以后还需更多学习呀.

对于这道题，我们求的是曼哈顿距离的最小值.

而维护的变量和以往是相同的，就是横纵坐标的最小值与最大值.

我们设为一个极为巧妙且玄学的股价函数.

int getdis(int o,int x1,int y1){

    int dis = 0;

    if(x1 < node[o].minv[0]) dis += node[o].minv[0] - x1;

    if(x1 > node[o].maxv[0]) dis += x1 - node[o].maxv[0];

    if(y1 < node[o].minv[1]) dis += node[o].minv[1] - y1;

    if(y1 > node[o].maxv[1]) dis += y1 - node[o].maxv[1];

    return dis;

 }

void query(int o,int x1,int y1){

    int dn = abs(node[o].p[0] - x1) + abs(node[o].p[1] - y1),dl,dr;

    ans = min(ans,dn);

    dl = node[o].ch[0] ? getdis(node[o].ch[0],x1,y1) : inf;

    dr = node[o].ch[1] ? getdis(node[o].ch[1],x1,y1) : inf;

    if(dl < dr) {

        if(dl < ans) query(node[o].ch[0],x1,y1);

        if(dr < ans) query(node[o].ch[1],x1,y1);

    }

    else {

        if(dr < ans) query(node[o].ch[1],x1,y1);

        if(dl < ans) query(node[o].ch[0],x1,y1);

    }

}

设当前矩阵的边界为 (x1,y1)，(x2,y2).

那么对于当前要查询的点 $p$ 如果在矩阵外，那么即使是最近距离也是 $p$ 到最近两个矩阵边界的曼哈顿距离和(getdis函数).

我们将上述最理想化距离设为 $w$，即点 $p$ 到矩阵边界的最小距离.

那么，如果点 $p$ 比当前最优解大的话，那么这一棵子树就没有必要查了.

Code:

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <cstdlib>

#define setIO(s) freopen(s".in","r",stdin)

#define maxn 3000000

#define inf 100000000

using namespace std;

namespace KDtree{

    int tot;

    int d;

    int ans;

    int n;

    int m;

    void init(){ tot = n, ans = inf;  }

    int newnode(){ return ++tot; }

    struct Data{

        int ch[2],minv[2],maxv[2],w,sum,p[2];

    }node[maxn];

    bool cmp(Data i,Data j){

        return i.p[d] == j.p[d] ? i.p[d^1] < j.p[d^1]: i.p[d] < j.p[d];

    }

    int isin(int o,int x1,int y1,int x2,int y2){

        if(node[o].minv[0]>=x1&&node[o].maxv[0]<=x2&&node[o].minv[1]>=y1&&node[o].maxv[1]<=y2) return 1;

        return 0;

    }

    int isout(int o,int x1,int y1,int x2,int y2){

        if(node[o].minv[0] > x2 || node[o].maxv[0] < x1) return 1;

        if(node[o].minv[1] > y2 || node[o].maxv[1] < y1) return 1;

        return 0;

    }

    void getmax(int &a,int b){ if( b > a ) a = b; }

    void getmin(int &a,int b){ if( b < a ) a = b; }

    void pushup(int o,int x){

        getmin(node[o].minv[0],node[x].minv[0]);

        getmin(node[o].minv[1],node[x].minv[1]);

        getmax(node[o].maxv[1],node[x].maxv[1]);

        getmax(node[o].maxv[0],node[x].maxv[0]);

        node[o].sum += node[x].sum;

    }

    int build(int l,int r,int o){

        int mid = (l + r) >> 1;

        d = o ; nth_element(node+l,node+mid,node+r+1,cmp);

        node[mid].minv[0] = node[mid].maxv[0] = node[mid].p[0];

        node[mid].minv[1] = node[mid].maxv[1] = node[mid].p[1];

        node[mid].sum = node[mid].w;

        node[mid].ch[0] = node[mid].ch[1] = 0;

        if(l < mid) node[mid].ch[0] = build(l,mid - 1,o ^ 1), pushup(mid,node[mid].ch[0]);

        if(r > mid) node[mid].ch[1] = build(mid + 1, r, o ^ 1), pushup(mid,node[mid].ch[1]);

        return mid;

    }

    void update(int &o,Data x,int de){

        if(!o) {

            o = newnode();

            node[o].p[0] = node[o].maxv[0] = node[o].minv[0] = x.p[0];

            node[o].p[1] = node[o].minv[1] = node[o].maxv[1] = x.p[1];

            return;

        }

        if(x.p[de] < node[o].p[de]) update(node[o].ch[0],x,de^1),pushup(o,node[o].ch[0]);

        else update(node[o].ch[1],x,de^1),pushup(o,node[o].ch[1]);

    }

    int getdis(int o,int x1,int y1){

        int dis = 0;

        if(x1 < node[o].minv[0]) dis += node[o].minv[0] - x1;

        if(x1 > node[o].maxv[0]) dis += x1 - node[o].maxv[0];

        if(y1 < node[o].minv[1]) dis += node[o].minv[1] - y1;

        if(y1 > node[o].maxv[1]) dis += y1 - node[o].maxv[1];

        return dis;

    }

    void query(int o,int x1,int y1){

        int dn = abs(node[o].p[0] - x1) + abs(node[o].p[1] - y1),dl,dr;

        ans = min(ans,dn);

        dl = node[o].ch[0] ? getdis(node[o].ch[0],x1,y1) : inf;

        dr = node[o].ch[1] ? getdis(node[o].ch[1],x1,y1) : inf;

        if(dl < dr) {

            if(dl < ans) query(node[o].ch[0],x1,y1);

            if(dr < ans) query(node[o].ch[1],x1,y1);

        }

        else {

            if(dr < ans) query(node[o].ch[1],x1,y1);

            if(dl < ans) query(node[o].ch[0],x1,y1);

        }

    }

    int main(){

        scanf("%d%d",&n,&m);

        init();

        for(int i = 1;i <= n; ++i) scanf("%d%d",&node[i].p[0],&node[i].p[1]);

        int root = build(1,n,0);

        for(int i = 1;i <= m; ++i) {

            int opt,a,b;

            scanf("%d%d%d",&opt,&a,&b);

            if(opt == 1) {

                Data k;

                k.p[0] = a,k.p[1] = b;

                update(root,k,0);

                if(i % 300000 == 0) root = build(1,tot,0);

            }

            if(opt == 2) {

                ans = inf;

                query(root,a,b);

                printf("%d\n",ans);

            }

        }

        return 0;

    }

};

int main(){

    //setIO("input");

    KDtree::main();

    return 0;

}

巴特西

bzoj 2648: SJY摆棋子 KDtree + 替罪羊式重构

最新文章

热门文章