kdtree bzoj4066

#include <iostream>
#include <algorithm>
//#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct node {
    int d[2], mx[2], mi[2], val, l, r;
    ll sum;
}p[200010];
int D;

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch>'9') { if (ch == '-')f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

 
bool operator == (const node a, const node b) {
    return (a.d[0] == b.d[0]) && (a.d[1] == b.d[1]);
}

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

bool in(int x11, int y11, int x22, int y22, int x33, int y33, int x44, int y44) {
    return (x11 <= x33) && (y11 <= y33) && (x22 >= x44) && (y22 >= y44);
}
bool out(int x11, int y11, int x22, int y22, int x33, int y33, int x44, int y44) {
    return (x11 > x44) || (y11 > y44) || (x22 < x33) || (y22 < y33);
}

struct KDTree {
    node tree[200010], tmp;
    int tot, rt;
    int dim = 2;
    void update(node &x) {
        int l = x.l, r = x.r;
        for (int i = 0; i < dim; i++) {
            x.mi[i] = x.mx[i] = x.d[i];
            if (l) {
                x.mi[i] = min(x.mi[i], tree[l].mi[i]);
                x.mx[i] = max(x.mx[i], tree[l].mx[i]);
            }
            if (r) {
                x.mi[i] = min(x.mi[i], tree[r].mi[i]);
                x.mx[i] = max(x.mx[i], tree[r].mx[i]);
            }
        }
        x.sum = x.val + tree[l].sum + tree[r].sum;
    }
    void insert(int k,int &x) {
        if(!x){
            x = ++tot;
            tree[x] = tmp; 
            return;
        }
        else if (tmp == tree[x]) {
            tree[x].val += tmp.val;
            tree[x].sum += tmp.val;
            return;
        }
        int ndim = (k + 1) % dim;
        if (tmp.d[k] < tree[x].d[k])insert(ndim, tree[x].l);
        else insert(ndim, tree[x].r);
        update(tree[x]);
    }
    ll query(int x1,int y1,int x2,int y2,int x) {
        ll sum = 0;
        if (in(x1,y1,x2,y2,tree[x].mi[0],tree[x].mi[1],tree[x].mx[0],tree[x].mx[1]))return tree[x].sum;
        if (out(x1, y1, x2, y2, tree[x].mi[0], tree[x].mi[1], tree[x].mx[0], tree[x].mx[1]))return 0;
        if (in(x1, y1, x2, y2, tree[x].d[0], tree[x].d[1], tree[x].d[0], tree[x].d[1]))sum += tree[x].val;
        sum += query(x1, y1, x2, y2, tree[x].l) + query(x1, y1, x2, y2, tree[x].r);
        return sum;
    }
    int rebuilt(int l,int r,int k) {
        if (l > r)return 0;
        int mid = (l + r) >> 1;
        D = k;
        int ndim = (k + 1) % dim;
        nth_element(p + l, p + mid, p + r + 1);
        tree[mid] = p[mid];
        tree[mid].l = rebuilt(l, mid-1, ndim);
        tree[mid].r = rebuilt(mid+1, r, ndim);
        update(tree[mid]);
        return mid;
    }
}T;

int main()
{
    int n = read();
    int times = 10000;
    ll ans = 0;
    while (true) {
        int op = read();
        if (op == 3)return 0;
        if (op == 1) {
            int x, y, val;
            x = read()^ans;
            y = read()^ans;
            val = read()^ans;
            T.tmp.d[0] = x;
            T.tmp.d[1] = y;
            T.tmp.sum = T.tmp.val = val;
            T.tmp.mi[0] = T.tmp.mx[0] = x;
            T.tmp.mi[1] = T.tmp.mx[1] = y;
            T.insert(0,T.rt);
            if (T.tot == times) {
                for (int i = 1; i <= T.tot; i++)p[i] = T.tree[i];
                T.rt = T.rebuilt(1, T.tot, 0);
                times += 10000;
            }
        }
        if (op == 2) {
            int x1, y1, x2, y2;
            x1 = read() ^ ans;
            y1 = read() ^ ans;
            x2 = read() ^ ans;
            y2 = read() ^ ans;
            if (x1 > x2)swap(x1, x2);
            if (y1 > y2)swap(y1, y2);
            ans = T.query(x1, y1, x2, y2, T.rt);
            printf("%lld
", ans);
        }
    }
    return 0;
}