洛谷P4148 简单题 题解 KD Tree + 替罪羊树

题目链接： https://www.luogu.com.cn/problem/P4148

题目大意：

两种操作：

平面内插入一个点；
查询一个矩形区域内所有点的权值和。
解题思路：

KD Tree模板题。

但是涉及插入操作，插入操作可能会导致树变得不平衡。

一棵子树如果不平衡，那怎么办？(\Rightarrow)

有没有一个支持重新建子树的平衡树，有。可以用 替罪羊树。

所以在 KD Tree 插入导致某棵子树不平衡时，将这棵子树以替罪羊树的方式 拍平 再 重建 即可。

示例程序：

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5;
const double alpha = 0.75;

struct Point {
    int dim[2], val;
} ord[maxn];    // 替罪羊树：用于保存拍平时的数据
int cnt;

struct Node {   // KD-Tree的结点
    int ls, rs;
    int mi[2], mx[2];   // mi[i]/mx[i]: 第i维的上下界
    int sum, sz;
    Point p;

    Node() {}
    Node(Point _p) {
        ls = rs = 0;
        for (int i = 0; i < 2; i++)
            mi[i] = mx[i] = _p.dim[i];
        sum = _p.val;
        sz = 1;
        p = _p;
    }

} tr[maxn];

stack<int> stk; // 保存释放掉的结点

int now, root, idx;

bool cmp(Point a, Point b) {
    return a.dim[now] < b.dim[now];
}

void push_up(int u) {
    int ls = tr[u].ls, rs = tr[u].rs;
    for (int i = 0; i < 2; i++) {
        tr[u].mi[i] = tr[u].mx[i] = tr[u].p.dim[i];
        if (ls) {
            tr[u].mi[i] = min(tr[u].mi[i], tr[ls].mi[i]);
            tr[u].mx[i] = max(tr[u].mx[i], tr[ls].mx[i]);
        }
        if (rs) {
            tr[u].mi[i] = min(tr[u].mi[i], tr[rs].mi[i]);
            tr[u].mx[i] = max(tr[u].mx[i], tr[rs].mx[i]);
        }
    }
    tr[u].sum = tr[u].p.val + tr[ls].sum + tr[rs].sum;
    tr[u].sz = 1 + tr[ls].sz + tr[rs].sz;
}

void slap(int u) {  // 替罪羊树：拍平
    if (!u) return;
    slap(tr[u].ls);
    ord[++cnt] = tr[u].p;
    stk.push(u);
    slap(tr[u].rs);
}

int build(int l, int r, int d) {   // 替罪羊树：建树
    if (l > r) return 0;
    int u;
    if (!stk.empty()) {
        u = stk.top();
        stk.pop();
    }
    else
        u = ++idx;
    int mid = (l + r) / 2;
    now = d;
    nth_element(ord+l, ord+mid, ord+r+1, cmp);
    tr[u].p = ord[mid];
    tr[u].ls = build(l, mid-1, d^1);
    tr[u].rs = build(mid+1, r, d^1);
    push_up(u);
    return u;
}

bool check_not_balance(int u) { // 替罪羊树：判断以u为根的子树是否不平衡
    int ls = tr[u].ls, rs = tr[u].rs;
    return max(tr[ls].sz, tr[rs].sz) > tr[u].sz * alpha;
}

void ins(int &u, Point p, int d) {
    if (!u) {
        if (!stk.empty()) {
            u = stk.top();
            stk.pop();
        }
        else
            u = ++idx;
        tr[u] = Node(p);
        return;
    }
    if (p.dim[d] < tr[u].p.dim[d])
        ins(tr[u].ls, p, d^1);
    else
        ins(tr[u].rs, p, d^1);
    push_up(u);
    if (check_not_balance(u)) {
        cnt = 0;
        slap(u);
        assert(cnt == tr[u].sz);
        u = build(1, cnt, d);
    }
}

int query(int u, int x1, int y1, int x2, int y2) {
    if (!u) return 0;
    int X1 = tr[u].mi[0], Y1 = tr[u].mi[1], X2 = tr[u].mx[0], Y2 = tr[u].mx[1];
    if (x1 <= X1 && X2 <= x2 && y1 <= Y1 && Y2 <= y2)
        return tr[u].sum;
    if (X2 < x1 || X1 > x2 || Y2 < y1 || Y1 > y2)
        return 0;
    int res = 0;
    int X = tr[u].p.dim[0], Y = tr[u].p.dim[1];
    if (x1 <= X && X <= x2 && y1 <= Y && Y <= y2)
        res += tr[u].p.val;
    res += query(tr[u].ls, x1, y1, x2, y2) + query(tr[u].rs, x1, y1, x2, y2);
    return res;
}

int n, op, ans;

int main() {
    scanf("%d", &n);
    while (~scanf("%d", &op)) {
        if (op == 1) {
            int x, y, val;
            scanf("%d%d%d", &x, &y, &val);
            x ^= ans;
            y ^= ans;
            val ^= ans;
            ins(root, Point{x, y, val}, 0);
        }
        else if (op == 2) {
            int x1, y1, x2, y2;
            scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
            x1 ^= ans;
            y1 ^= ans;
            x2 ^= ans;
            y2 ^= ans;
            ans = query(root, x1, y1, x2, y2);
            printf("%d\n", ans);
        }
        else // op == 3
            break;
    }
    return 0;
}

洛谷P4148 简单题 题解 KD Tree + 替罪羊树