KDTree(Bzoj2648: SJY摆棋子)

╰+攻爆jí腚メ 2021-12-23 07:53 275阅读 0赞

# 题面 #

[传送门][Link 1]

# KDTree #

大概就是一个分割\\(k\\)维空间的数据结构，二叉树

建立：每层选取一维为关键字，把中间的点拿出来，递归左右，有个\\(STL\\)函数nth\_element可以用一下

维护：维护当前这个点的子树的每一维的最大值和最小值，相当于维护了个高维矩形

查询：直接遍历一棵树是\\(O(n)\\)的，利用一些独特的性质可以剪枝，因题而异

奇技淫巧：

1.  把坐标绕原点转\\(\\alpha\\)度
2.  定期重构或者像替罪羊树一样，利用平衡因子判断是否需重构
3.  每次查询到某一层优先选取答案可能最优的一个儿子先递归
4.  等等

# Sol #

\\(KDTree\\)模板题  
利用替罪羊树的思想重构

# include <bits/stdc++.h>
    # define IL inline
    # define RG register
    # define Fill(a, b) memset(a, b, sizeof(a))
    using namespace std;
    typedef long long ll;
    
    IL int Input(){
        RG int x = 0, z = 1; RG char c = getchar();
        for(; c < '0' || c > '9'; c = getchar()) z = c == '-' ? -1 : 1;
        for(; c >= '0' && c <= '9'; c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);
        return x * z;
    }
    
    const int maxn(1e6 + 5);
    const int inf(2e9);
    const double alpha(0.75);
    
    int n, op, rt, q, ans, p[maxn], tot, num, cnt;
    
    struct Point{
        int d[2];
    
    
        IL int operator <(RG Point a) const{
            return d[op] < a.d[op];
        }
    } a[maxn];
    
    struct KDTree{
        int ch[2], d[2], size;
        int mn[2], mx[2];
    } tr[maxn];
    
    IL void Chkmax(RG int &x, RG int y){
        if(y > x) x = y;
    }
    
    IL void Chkmin(RG int &x, RG int y){
        if(y < x) x = y;
    }
    
    IL int NewNode(){
        return tot ? p[tot--] : ++cnt;
    }
    
    IL void Update(RG int x){
        RG int ls = tr[x].ch[0], rs = tr[x].ch[1];
        tr[x].mx[0] = tr[x].mn[0] = tr[x].d[0];
        tr[x].mx[1] = tr[x].mn[1] = tr[x].d[1];
        tr[x].size = tr[ls].size + tr[rs].size + 1;
        if(ls){
            Chkmin(tr[x].mn[0], tr[ls].mn[0]), Chkmin(tr[x].mn[1], tr[ls].mn[1]);
            Chkmax(tr[x].mx[0], tr[ls].mx[0]), Chkmax(tr[x].mx[1], tr[ls].mx[1]);
        }
        if(rs){
            Chkmin(tr[x].mn[0], tr[rs].mn[0]), Chkmin(tr[x].mn[1], tr[rs].mn[1]);
            Chkmax(tr[x].mx[0], tr[rs].mx[0]), Chkmax(tr[x].mx[1], tr[rs].mx[1]);
        }
    }
    
    IL int Build(RG int l, RG int r, RG int nop){
        op = nop;
        RG int x = (l + r) >> 1, nw = NewNode();
        nth_element(a + l, a + x, a + r + 1);
        tr[nw].d[0] = a[x].d[0], tr[nw].d[1] = a[x].d[1];
        if(l < x) tr[nw].ch[0] = Build(l, x - 1, nop ^ 1);
        if(x < r) tr[nw].ch[1] = Build(x + 1, r, nop ^ 1);
        Update(nw);
        return nw;
    }
    
    IL int Check(RG int x){
        return alpha * tr[x].size < tr[tr[x].ch[0]].size || alpha * tr[x].size < tr[tr[x].ch[1]].size;
    }
    
    IL void ReCycle(RG int x){
        if(!x) return;
        ReCycle(tr[x].ch[0]), tr[x].ch[0] = 0;
        p[++tot] = x, a[++num].d[0] = tr[x].d[0], a[num].d[1] = tr[x].d[1];
        ReCycle(tr[x].ch[1]), tr[x].ch[1] = 0;
    }
    
    IL int ReBuild(RG int x, RG int nop){
        num = 0, ReCycle(x);
        return Build(1, num, nop);
    }
    
    IL void Insert(RG int &x, RG int nop, RG Point np){
        if(!x){
            x = NewNode();
            tr[x].d[0] = np.d[0], tr[x].d[1] = np.d[1];
            tr[x].mx[0] = tr[x].mn[0] = tr[x].d[0];
            tr[x].mx[1] = tr[x].mn[1] = tr[x].d[1];
            return;
        }
        if(np.d[nop] < tr[x].d[nop]) Insert(tr[x].ch[0], nop ^ 1, np);
        else Insert(tr[x].ch[1], nop ^ 1, np);
        Update(x);
        if(Check(x)) x = ReBuild(x, nop);
    }
    
    IL int Calc(RG int x, RG Point np){
        RG int d = max(np.d[0] - tr[x].mx[0], 0) + max(tr[x].mn[0] - np.d[0], 0);
        return d + max(tr[x].mn[1] - np.d[1], 0) + max(np.d[1] - tr[x].mx[1], 0);
    }
    
    IL void Query(RG int x, RG Point np){
        RG int d = abs(tr[x].d[0] - np.d[0]) + abs(tr[x].d[1] - np.d[1]), d1 = inf, d2 = inf;
        Chkmin(ans, d);
        if(tr[x].ch[0]) d1 = Calc(tr[x].ch[0], np);
        if(tr[x].ch[1]) d2 = Calc(tr[x].ch[1], np);
        RG int c = 0;
        if(d1 > d2) swap(d1, d2), c ^= 1;
        if(d1 < ans) Query(tr[x].ch[c], np);
        if(d2 < ans) Query(tr[x].ch[!c], np);
    }
    
    int main(){
        n = Input(), q = Input();
        for(RG int i = 1; i <= n; ++i) a[i].d[0] = Input(), a[i].d[1] = Input();
        rt = Build(1, n, 0);
        for(RG int i = 1; i <= q; ++i){
            RG int t = Input(), x = Input(), y = Input();
            if(t == 1) Insert(rt, 0, (Point){x, y});
            else{
                ans = inf;
                Query(rt, (Point){x, y});
                printf("%d\n", ans);
            }
        }
        return 0;
    }

转载于:https://www.cnblogs.com/cjoieryl/p/9113780.html

[Link 1]: https://www.lydsy.com/JudgeOnline/problem.php?id=2648