k-d Tree 20pts 求条

rt

/*Code By Manipula*/
#include <bits/stdc++.h>
#define endl '\n'
#define INF 0x3f3f3f3f
// #define int long long
#define fi first
#define sc second
#define lb lower_bound
#define YES printf("YES\n")
#define Yes printf("Yes\n")
#define NO printf("NO\n")
#define No printf("No\n")
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define Debug(fmt, arg...) fprintf(stderr, fmt, ##arg)
#define DEBUG() debug("In Function [%s] Line %d\n", __FUNCTION__, __LINE__) 

const int N = 5e5 + 5;
const double alpha = 0.75;

struct Point {
    int x[2], val;
} a[N];

int fr[N];
int n, rt, tot, cnt, top, lstAns;

namespace KD_Tree {
    struct Node {
        int ls, rs, L[2], R[2], sum, siz;
        Point P;

        #define ls(p) (tr[p].ls)
        #define rs(p) (tr[p].rs)
    } tr[N];

    void init() {
        tr[0].L[0] = tr[0].L[1] = INF;
        tr[0].R[0] = tr[0].R[1] = -INF;
    }

    void pushup(int p) {
        auto L = tr[ls(p)], R = tr[rs(p)];

        tr[p].sum = tr[p].P.val + L.sum + R.sum;
        tr[p].siz = L.siz + R.siz + 1;

        for (int i = 0; i <= 1; i++) {          
            tr[p].L[i] = std::min(tr[p].P.x[i], L.L[i]);
            tr[p].R[i] = std::max(tr[p].P.x[i], R.R[i]);
        }
    }

    int Add() { return !top ? ++tot : fr[top--]; }

    int Rebuild(int l, int r, int D) {
        if (l > r)return 0;
        int mid = (l + r) >> 1;
        int p = Add();

        std::nth_element(a + l, a + mid, a + r + 1, [&](Point A, Point B) { return A.x[D] < B.x[D]; });
        tr[p].P = a[mid];

        ls(p) = Rebuild(l, mid - 1, D ^ 1);
        rs(p) = Rebuild(mid + 1, r, D ^ 1);
        pushup(p);

        return p;
    }

    void slap(int p) {
        if (!p)return;

        slap(ls(p));
        fr[++top] = p, a[++cnt] = tr[p].P;
        slap(rs(p));
    }

    void Work(int &p, int D) {
        if (tr[p].siz * alpha <= tr[ls(p)].siz || tr[p].siz * alpha <= tr[rs(p)].siz)
            cnt = 0, slap(p), p = Rebuild(1, tr[p].siz, D);
    }

    void Insert(int &p, Point P, int D) {
        if (!p)return p = Add(), ls(p) = rs(p) = 0, tr[p].P = P, pushup(p);

        if (P.x[D] <= tr[p].P.x[D])Insert(ls(p), P, D ^ 1);
        else Insert(rs(p), P, D ^ 1);

        pushup(p);
        Work(p, D);
    }

    int Query(int p, int x1, int y1, int x2, int y2) {
        if (!p)return 0;

        if (x1 <= tr[p].L[0] && tr[p].R[0] <= x2 && y1 <= tr[p].L[1] && tr[p].R[1] <= y2)
            return tr[p].sum;

        if (tr[p].L[0] < x1 || tr[p].R[0] > x2 || tr[p].L[1] < y1 || tr[p].R[1] > y2)
            return 0;

        int ans = 0;
        if (x1 <= tr[p].P.x[0] && tr[p].P.x[0] <= x2 && y1 <= tr[p].P.x[1] && tr[p].P.x[1] <= y2)
            ans += tr[p].P.val;

        ans += Query(ls(p), x1, y1, x2, y2) + Query(rs(p), x1, y1, x2, y2);

        return ans;
    }
}

signed main() {
    // freopen(".in", "r", stdin);
    // freopen(".out", "w", stdout);

    int opt;

    scanf("%d", &n);

    KD_Tree::init();

    while (scanf("%d", &opt), opt != 3) {
        if (opt == 1) {
            int x, y, k; scanf("%d%d%d", &x, &y, &k);
            x ^= lstAns, y ^= lstAns, k ^= lstAns;

            KD_Tree::Insert(rt, (Point){x, y, k}, 0);
        }
        else {
            int x1, y1, x2, y2; scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
            x1 ^= lstAns, x2 ^= lstAns, y1 ^= lstAns, y2 ^= lstAns;

            printf("%d\n", lstAns = KD_Tree::Query(rt, x1, y1, x2, y2));
        }
    }

    return 0;
}