简单题（K-D Tree+单点插入+矩形区间和）

简单题

不知道为什么取这个名字QAQ，有个地方初始化不对，在洛谷上挂了一页。

题意：
特点： 强制在线(last_ans)+20M内存限制

思路： 没啥思路，就是K-D Tree板子题，因此下面记录K-D Tree的一些信息

1. K-D Tree也算二叉+平衡+树吧？用于维护K-Dimension的信息，将K维空间不断地通过某一维度的中位数点进行当前空间的分割。
2. 特点：树的节点数跟空间中点数相同（动态开点+节点回收），平衡时高度为 $\left[lo{g}_{2}n\right]$[log2​n]
3. 一些需要维护的基础信息：
   1. $lson，rson:$lson，rson:当前节点左儿子+右儿子
   2. $sum:$sum:当前子树的所有节点权值和
   3. $size:$size:当前子树节点总数
   4. $point:$point:当前节点所代表的空间中的一个点
   5. $mi\left[i\right]:$mi[i]:当前子树空间中第 $i$i维的下界
   6. $mx\left[i\right]:$mx[i]:当前子树空间中第 $i$i维的上界
4. 一些常用基础函数：
   1. nth_element(tp+l,tp+m,tp+r+1); 用于 $lo{g}_{2}n$log2​n时间复杂度选出中点且将数组分成两边
   2. void rebuild(int l, int r, int dim, int &now);重构时调用的建树
   3. void to_array(int idx, int now);重构前将当前子树转化为数组并存在某临时数组中
   4. void check(int dim, int &now);检查当前子树是否相对平衡
   5. void insert(P np, int dim, int &now);插入一个新的点

代码

#include "bits/stdc++.h"
#define hhh printf("hhh\n")
#define see(x) (cerr<<(#x)<<'='<<(x)<<endl)
using namespace std;
inline int read() {int x=0,f=1;char c=getchar();while(c!='-'&&(c<'0'||c>'9'))c=getchar();if(c=='-')f=-1,c=getchar();while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return f*x;}

const int maxn = 2e5+10;

struct P{ int x[2], w; }p[maxn], tp[maxn];
int ls[maxn], rs[maxn], sum[maxn], sz[maxn];
int mi[maxn][2], mx[maxn][2];
int rub[maxn], top, tot, Dim, rt;
int N, last_ans;

bool operator < (P a, P b) { return a.x[Dim]<b.x[Dim]; }

inline void Min(int &x, int y) { if(x>y) x=y; }
inline void Max(int &x, int y) { if(x<y) x=y; }

int newnode() {
    if(top) return rub[top--];
    return ++tot;
}

void push_up(int now) {
    for(int i=0; i<2; ++i) {
        mi[now][i]=mx[now][i]=p[now].x[i];
        if(ls[now]) Min(mi[now][i],mi[ls[now]][i]), Max(mx[now][i],mx[ls[now]][i]);
        if(rs[now]) Min(mi[now][i],mi[rs[now]][i]), Max(mx[now][i],mx[rs[now]][i]);
    }
    sum[now]=sum[ls[now]]+sum[rs[now]]+p[now].w;
    sz[now]=sz[ls[now]]+sz[rs[now]]+1;
}

void rebuild(int l, int r, int dim, int &now) {
    if(l>r) { now=0; return; } //千万别忘了now=0！！！
    now=newnode();
    int m=(l+r)/2;
    Dim=dim; nth_element(tp+l,tp+m,tp+r+1); p[now]=tp[m];
    rebuild(l,m-1,dim^1,ls[now]); rebuild(m+1,r,dim^1,rs[now]);
    push_up(now);
}

void to_array(int idx, int now) {
    if(ls[now]) to_array(idx,ls[now]);
    tp[idx+sz[ls[now]]]=p[now]; rub[++top]=now;
    if(rs[now]) to_array(idx+sz[ls[now]]+1,rs[now]);
}

void check(int dim, int &now) {
    if(sz[now]*3<sz[ls[now]]*4||sz[now]*3<sz[rs[now]]*4) {
        to_array(1,now); rebuild(1,sz[now],dim,now);
    }
}

void insert(P np, int dim, int &now) {
    if(!now) {
        now=newnode(), ls[now]=rs[now]=0;
        p[now]=np;
        push_up(now);
        return;
    }
    if(np.x[dim]<=p[now].x[dim]) insert(np,dim^1,ls[now]);
    else insert(np,dim^1,rs[now]);
    push_up(now); check(dim,now);
}

inline bool in(int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4) {
    return x1>=x3&&y1>=y3&&x2<=x4&&y2<=y4;
}
inline bool out(int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4) {
    return x1>x4||x2<x3||y1>y4||y2<y3;
}

int query(int x1, int y1, int x2, int y2, int now) {
    if(!now) return 0;
    if(out(mi[now][0],mi[now][1],mx[now][0],mx[now][1],x1,y1,x2,y2)) return 0;
    if(in(mi[now][0],mi[now][1],mx[now][0],mx[now][1],x1,y1,x2,y2)) return sum[now];
    if(in(p[now].x[0],p[now].x[1],p[now].x[0],p[now].x[1],x1,y1,x2,y2))
        return p[now].w+query(x1,y1,x2,y2,ls[now])+query(x1,y1,x2,y2,rs[now]);
    return query(x1,y1,x2,y2,ls[now])+query(x1,y1,x2,y2,rs[now]);
}

int main() {
    N=read();
    int op;
    while(scanf("%d", &op), op!=3) {
        if(op==1) {
            int x=read()^last_ans, y=read()^last_ans, A=read()^last_ans;
            insert((P){x,y,A},0,rt);
        }
        else {
            int x1=read()^last_ans, y1=read()^last_ans, x2=read()^last_ans, y2=read()^last_ans;
            printf("%d\n", last_ans=query(x1,y1,x2,y2,rt));
        }
    }
}