BZOJ 4066 简单题（K-D Tree）解题报告

2017-10-26 3,015 次浏览 解题报告

解题思路

本题是要求实现对点更新和矩形区域的查询操作，强制在线。于是很容易和 K-D Tree 的按区域管辖和合并的性质联系到一起。本题需要对在矩形内外的判断细心留意，以免出错。

另外由于本题大量的插入操作，K-D Tree 可能随着数据量增大导致结构不平衡，从而影响效率。因此这里我们需要用到类似替罪羊树的思想，引入一个平衡因子（这里我设置了 0.7），一旦某一侧子树的 size 过大（所占比例超过平衡因子规定的临界值），就重建这颗树，以此来保证效率。当然直接按插入次数暴力重建整棵树也是可以的。

参考代码

按平衡因子重建

#include <cstdio>
#include <algorithm>
using namespace std;

const int INF = 0x3f3f3f3f;
const int MAXN = 200001;
const int MAXK = 2;
const int K = 2;
const double MAXRBR = 0.7;

struct node {
    int v, sum, size, D;
    int d[MAXK];
    int min[MAXK], max[MAXK];
    int l, r;
} t[MAXN];

struct info {
    int min[MAXK], max[MAXK];
    info() {}
    info(int mn[], int mx[]) {
        for(int i=0; i<K; ++i) {
            min[i] = mn[i];
            max[i] = mx[i];
        }
    }
} q;

int D, root, n, p[MAXK], cnt, tlist[MAXN];

bool cmp(int a, int b) {
    return t[a].d[D] < t[b].d[D];
}

void Update(int x) {
    int l = t[x].l, r = t[x].r;
    for(int i=0; i<K; ++i) {
        t[x].min[i] = min(t[x].min[i], min(t[l].min[i], t[r].min[i]));
        t[x].max[i] = max(t[x].max[i], max(t[l].max[i], t[r].max[i]));
    }
    t[x].sum = t[l].sum + t[r].sum + t[x].v;
    t[x].size = t[l].size + t[r].size + 1;
}

int Build(int l, int r, int d) {
    D = d;
    int mid = (l+r) >> 1;
    nth_element(tlist+l, tlist+mid, tlist+r+1, cmp);
    int x = tlist[mid];
    for(int i=0; i<K; ++i) {
        t[x].min[i] = t[x].max[i] = t[x].d[i];
    }
    t[x].D = d;
    if(mid != l) t[x].l = Build(l, mid-1, d^1);
    else t[x].l = 0;
    if(mid != r) t[x].r = Build(mid+1, r, d^1);
    else t[x].r = 0;
    Update(x);

    return x;
}

void DFS(int x){
    if(!x) return;
    DFS(t[x].l);
    tlist[++cnt] = x;
    DFS(t[x].r);
}

void Rebuild(int &x){
    cnt = 0;
    DFS(x);
    x = Build(1, cnt, t[x].D);
}

void Insert(int &x, int v, int d) {
    if(!x) {
        x = ++n;
        for(int i=0; i<K; ++i) {
            t[x].min[i] = t[x].max[i] = t[x].d[i] = p[i];
        }
        t[x].D = d;
        t[x].sum = t[x].v = v;
        t[x].size = 1;
        t[x].l = t[x].r = 0;
        return;
    }
    if(t[x].d[0]==p[0] && t[x].d[1]==p[1]) {
        t[x].sum += v;
        t[x].v += v;
        return;
    }
    if(p[d] < t[x].d[d]) {
        Insert(t[x].l, v, d^1);
        Update(x);
        if(t[t[x].l].size > MAXRBR*t[x].size) Rebuild(x);
    }
    else {
        Insert(t[x].r, v, d^1);
        Update(x);
        if(t[t[x].r].size > MAXRBR*t[x].size) Rebuild(x);
    }
}

bool In(info p, info q) {
    for(int i=0; i<K; ++i) {
        if(p.min[i]<q.min[i] || p.max[i]>q.max[i]) return false;
    }

    return true;
}

bool Out(info p, info q) {
    for(int i=0; i<K; ++i) {
        if(p.max[i]<q.min[i] || p.min[i]>q.max[i]) return true;
    }

    return false;
}

int Query(int x) {
    if(!x) return 0;
    if(In((info){t[x].min, t[x].max}, q)) return t[x].sum;
    if(Out((info){t[x].min, t[x].max}, q)) return 0;
    int ret = 0;
    info tmp;
    for(int i=0; i<K; ++i) {
        tmp.min[i] = tmp.max[i] = t[x].d[i];
    }
    if(In(tmp, q)) ret += t[x].v;
    ret += Query(t[x].l);
    ret += Query(t[x].r);

    return ret;
}

int main(int argc, char const *argv[]) {
    int op, v, ans = 0;
    scanf("%*d");
    for(int i=0; i<K; ++i) {
        t[0].min[i] = INF;
        t[0].max[i] = -INF;
    }
    while(true) {
        scanf("%d", &op);
        if(op == 1) {
            scanf("%d %d %d", &p[0], &p[1], &v);
            p[0] ^= ans;
            p[1] ^= ans;
            v ^= ans;
            Insert(root, v, 0);
        }
        if(op == 2) {
            scanf("%d %d %d %d", &q.min[0], &q.min[1], &q.max[0], &q.max[1]);
            q.min[0] ^= ans;
            q.min[1] ^= ans;
            q.max[0] ^= ans;
            q.max[1] ^= ans;
            ans = Query(root);
            printf("%d\n", ans);
        }
        if(op == 3) break;
    }
    
    return 0;
}

按插入次数重建

#include <cstdio>
#include <algorithm>
using namespace std;

const int INF = 0x3f3f3f3f;
const int MAXN = 200001;
const int MAXK = 2;
const int K = 2;
const int MAXRBN = 5000;

struct node {
    int v, sum;
    int d[MAXK];
    int min[MAXK], max[MAXK];
    int l, r;
} t[MAXN];

struct info {
    int min[MAXK], max[MAXK];
    info() {}
    info(int mn[], int mx[]) {
        for(int i=0; i<K; ++i) {
            min[i] = mn[i];
            max[i] = mx[i];
        }
    }
} q;

int D, root, n, p[MAXK];

bool cmp(node a, node b) {
    return a.d[D] < b.d[D];
}

void Update(int x) {
    int l = t[x].l, r = t[x].r;
    for(int i=0; i<K; ++i) {
        t[x].min[i] = min(t[x].min[i], min(t[l].min[i], t[r].min[i]));
        t[x].max[i] = max(t[x].max[i], max(t[l].max[i], t[r].max[i]));
    }
    t[x].sum = t[l].sum + t[r].sum + t[x].v;
}

int Build(int l, int r, int d) {
    D = d;
    int mid = (l+r) >> 1;
    nth_element(t+l, t+mid, t+r+1, cmp);
    for(int i=0; i<K; ++i) {
        t[mid].min[i] = t[mid].max[i] = t[mid].d[i];
    }
    if(mid != l) t[mid].l = Build(l, mid-1, d^1);
    else t[mid].l = 0;
    if(mid != r) t[mid].r = Build(mid+1, r, d^1);
    else t[mid].r = 0;
    Update(mid);

    return mid;
}

void Insert(int &x, int v, int d) {
    if(!x) {
        x = ++n;
        for(int i=0; i<K; ++i) {
            t[x].min[i] = t[x].max[i] = t[x].d[i] = p[i];
        }
        t[x].sum = t[x].v = v;
        t[x].l = t[x].r = 0;
        return;
    }
    if(t[x].d[0]==p[0] && t[x].d[1]==p[1]) {
        t[x].sum += v;
        t[x].v += v;
        return;
    }
    if(p[d] < t[x].d[d]) Insert(t[x].l, v, d^1);
    else Insert(t[x].r, v, d^1);
    Update(x);
}

bool In(info p, info q) {
    for(int i=0; i<K; ++i) {
        if(p.min[i]<q.min[i] || p.max[i]>q.max[i]) return false;
    }

    return true;
}

bool Out(info p, info q) {
    for(int i=0; i<K; ++i) {
        if(p.max[i]<q.min[i] || p.min[i]>q.max[i]) return true;
    }

    return false;
}

int Query(int x) {
    if(!x) return 0;
    if(In((info){t[x].min, t[x].max}, q)) return t[x].sum;
    if(Out((info){t[x].min, t[x].max}, q)) return 0;
    int ret = 0;
    info tmp;
    for(int i=0; i<K; ++i) {
        tmp.min[i] = tmp.max[i] = t[x].d[i];
    }
    if(In(tmp, q)) ret += t[x].v;
    ret += Query(t[x].l);
    ret += Query(t[x].r);

    return ret;
}

int main(int argc, char const *argv[]) {
    int op, v, cnt = 0, ans = 0;
    scanf("%*d");
    for(int i=0; i<K; ++i) {
        t[0].min[i] = INF;
        t[0].max[i] = -INF;
    }
    while(true) {
        scanf("%d", &op);
        if(op == 1) {
            scanf("%d %d %d", &p[0], &p[1], &v);
            p[0] ^= ans;
            p[1] ^= ans;
            v ^= ans;
            Insert(root, v, 0);
            cnt++;
            if(cnt == MAXRBN) {
                root = Build(1, n, 0);
                cnt = 0;
            }
        }
        if(op == 2) {
            scanf("%d %d %d %d", &q.min[0], &q.min[1], &q.max[0], &q.max[1]);
            q.min[0] ^= ans;
            q.min[1] ^= ans;
            q.max[0] ^= ans;
            q.max[1] ^= ans;
            ans = Query(root);
            printf("%d\n", ans);
        }
        if(op == 3) break;
    }
    
    return 0;
}

由 bLue 创作，采用 知识共享署名 3.0，可自由转载、引用，但需署名作者且注明文章出处。
本文地址：https://dreamer.blue/blog/post/2017/10/26/bzoj-4066.dream

还不快抢沙发

添加新评论