也许有些同学还不了解 \text{K-D Tree} 这种数据结构，这是一种基于暴力优化的“玄学”数据结构，“D”是维度的意思，“K”是维度常数。
$(1,2),(2,6),(5,3),(3,5),(4,4)$ 这五个点可以构建这样一颗 $\text{K-D Tree}$：
每个节点需要记下每一个维度的极值用来剪枝，例如查询第一维的范围是 $[3,5]$，那么在到达节点 $(1,2)$ 时，发现子树第一维的值域是 $[1,2]$，与查询区间无交集，这时可以立即退出，起到剪枝作用。
如何静态构建 $\text{K-D Tree}$?
$\text{K-D Tree}$ 的在数据区间 $[l,r]$ 建树的过程如下：
1. 令 $mid=(l+r)/2$，将 $mid$ 置于按维度 $a$ 排序后的位置，调用如下函数即可
```cpp
std::nth_element(a+l,a+mid,a+r+1,cmp)
```
2. 递归建树 $[l,mid-1]$ 和 $[mid+1,r]$；
3. 记录两个维度的极值（用来剪枝）。
代码实现
```cpp
inline void Maintain(int x){
lx[x]=rx[x]=a[x].x;ly[x]=ry[x]=a[x].y;
if(lc[x])lx[x]=min(lx[x],lx[lc[x]]),rx[x]=max(rx[x],rx[lc[x]]),
ly[x]=min(ly[x],ly[lc[x]]),ry[x]=max(ry[x],ry[lc[x]]);
if(rc[x])lx[x]=min(lx[x],lx[rc[x]]),rx[x]=max(rx[x],rx[rc[x]]),
ly[x]=min(ly[x],ly[rc[x]]),ry[x]=max(ry[x],ry[rc[x]]);
return;
}
int build(int l,int r){
if(r<l)return 0;int mid=l+((r-l)>>1),i;
nth_element(a+l,a+mid,a+r+1,cmpx);
lc[mid]=build(l,mid-1);
rc[mid]=build(mid+1,r);
Maintain(mid);return mid;
}
```
以上的建树过程并没有发挥出 $\text{K-D Tree}$ 的真正作用，毕竟完全按照 $x$ 维建树，容易通过给出 $x$ 维相近，$y$ 维差别很大的数据进行 Hack，他能通过加强版全部数据，但在下面例一中，它完美地起到了“[卡评测](/record/64077817)”的作用。于是，我们考虑进行改进。
这里引入 $\text{K-D Tree}$ 的第二种构建方法：交替构建。即若某一棵子树以某一维建树，它的儿子就要以相反的标准建树，实现也十分简单：
```cpp
int build(int l,int r,bool Tp){
if(r<l)return 0;int mid=l+((r-l)>>1),x;
if(Tp)nth_element(Id+l,Id+mid,Id+r+1,cmpx);
else nth_element(Id+l,Id+mid,Id+r+1,cmpy);x=Id[mid];
lc[x]=build(l,mid-1,Tp^1);rc[x]=build(mid+1,r,Tp^1);Maintain(x);
return x;
}
```
$\text{K-D Tree}$ 是可以动态插入的，由于它分层（每一层排序的维度不同）的特点，需要采用替罪羊树的思想，确定一个重构指数 $\alpha\in(0.65,0.85)$，当某一个儿子占比超过 $\alpha$，就将整棵树的节点全部取出，重新建树，一次插入如有多棵需要重构，应只重构深度最浅的那棵，这样保证了树的高度是 $O(\log_2n)$ 的，代码见【五】**本文所有完整代码后附**。
从例题五的[题解](/blog/502410/linear-space-online-2D-points-p4148)中可以得到另一种严格 $O(\sqrt n)$ 的动态插入方式。
---
$\text{Update on 2022-11-05:}
由于 \text{K-D Tree} 的复杂度对于树的平衡有高度的要求，所以替罪羊式重构并不能做到 O(\sqrt n)，只能说基本够用，作者之前并没有意识到这一点，但做的题目都能通过。
如果想要保证查询复杂度为 O(\sqrt n)，可以进行二进制分组，具体地，插入时新建一棵只有一个节点的 \text{K-D Tree}，并将所有等大的 \text{K-D Tree} 合并，可以参考二项堆，可以证明，插入的平摊复杂度为 O(n\log_2^2n)，比之前的做法优秀很多。
如果你需要进行可持久化，目前我能想到的算法均需要使用随机数，目前全网找不到可持久化 \text{K-D Tree} 的题目，也不在本文讨论范围。
Part1 邻值查询
例题一 [P7883 平面最近点对（加强加强版）](/problem/P7883)。
题意大致是，给定 $n\le 4\times 10^5$ 个点，求最近点对距离的平方。
关于最近点对问题，$\text{K-D Tree}$ 解法分为如下几个步骤：
1. 静态构建 $\text{K-D Tree}$；
2. 对每个点进行查询操作（相同的点特判）。
在构建 $\text{K-D Tree}$ 之后，利用 $l$、$r$ 的极值，我们可以进行有效剪枝，首先，对于每棵子树，不难构造如下的估价函数，即在该区间内查找最理想的答案：
```cpp
inline ll fac(int x){
if(!x)return T+50;ll res=0;
if(lx[x]>a[nowt].x)res+=P(lx[x]-a[nowt].x);
if(rx[x]<a[nowt].x)res+=P(a[nowt].x-rx[x]);
if(ly[x]>a[nowt].y)res+=P(ly[x]-a[nowt].y);
if(ry[x]<a[nowt].y)res+=P(a[nowt].y-ry[x]);
return res;
}
```
然后，采用启发式搜索的思想，就得出了本题的代码【一】。虽然这样起到了剪枝的作用，但评测效果却并不理想，[仍有两个点超时](/record/62650150)。
回到根本，交替构建是为了防止某一维十分相近的特殊情况，我们可以通过计算方差来判断应当使用的维度，每次选取方差较大的维度进行建树，这样起到了较好的效果，自然也得到了满分【二】。
例题二 [ P4357【CQOI2016】K 远点对](/problem/P4357)
同样给了 $n\le10^5$ 个二维数点，需要我们查找第 $K\le100$ 远的点对。
为了方便，我们将 $K$ 翻倍，这样任意点对 $(x,y)$ 都可以无需特判地计算两次。维护一个小根堆，表示当前最远的 $K$ 组点对的距离，那么每一次只有超过当前第 $K$ 远的点对才会对优先队列产生影响，每次得到大于堆顶元素的距离时，用它代替堆顶，最后剩下的堆顶就是答案。由于数据范围极小，交替建树的程序可以得到最优解【三】。
例题三 [P4475 巧克力王国](/problem/P4475)
大致题意是对于 $ax+by\le c$ 的数点权值求和。
使用二维 $\text{K-D Tree}$ 对二维数点坐标极值进行维护，在查询时进行剪枝。不管查询数的正负，都会有 $\max ax=\max\{a\max x,a\min x\},\max by=\max\{b\max y,b\min y\}$（用一次函数的图像证明）。若最大的 $ax,by$ 都满足条件，那么整棵树都满足条件，可以直接加上，如果最小的都不满足，就可以直接退出。由于数据放得很松，只需要交替建树就能通过（你想方差建树也可以）：【四】
例题四 [P4169【Violet】天使玩偶/SJY摆棋子](/problem/P4169)
动态插入二维数点，求最近曼哈顿距离的点。
可以分四个方向讨论，转化为矩形查询，用 CDQ 分治可以做到 $O(q\log_2^2n)$，但也可以用动态插入的 $\text{K-D Tree}$ 记录坐标最值进行邻值查询。
同样有 当 $x_i\notin[\min x,\max x]$ 时，有 $\min|x-x_i|=\min\{|\max x-x_i|,|\min x-x_i|\}$，于是可以类似地剪枝。
可以得到最优解【五】 $\text{(test on 2022-08-04)}$。
### Part2 矩形查询
在例四中提到，可以分四类讨论转化为矩形查询问题，那么既然可以剪枝，为什么要转化呢？因为，矩形查询的 $\text{K-D Tree}$ 如果采用交替建树，是可以证明最坏复杂度是 $O(n\log_2n+qn^{\frac{k-1}{k}})$，理由是，每一次向下走时，有一维会被剪枝掉（即 $\text{K-D Tree}$ 在这一层是按该维排序的），当 $k=2$ 时，复杂度为 $O(q\sqrt n)$，十分优秀。
例题五 [P4148 简单题](/problem/P4148)
$n\le5\times10^5$ 次询问，每次给点 $(x,y)$ 的权值加上数字 $A$，或查询矩形 $(x_1,y_1),(x_2,y_2)$ 内权值和，强制在线 $\text{(8s,20MB)}$。
这道题凸显了 $\text{K-D Tree}$ 的优势：支持在线插入查询，空间复杂度为 $O(n)$，同时卡掉了 $\text{CDQ}$ 分治和树套树。似乎可以使用分块套平衡树，能通过但没有 $\text{K-D Tree}$ 快。
考虑动态插入，维护每一棵树的大小，权值和，两维的极值，就可以进行有效剪枝【六】。
例题六 [【模板】三维偏序（陌上花开）](/problem/P3810)
有 $n\le10^5$ 个三维数点，求 $a_x\le a_y,b_x\le b_y,c_x\le c_y$ 的有序数对 $(x,y)$ 个数。
先按 $a_i$ 排序，再从小到大将 $(b_i,c_i)$ 插入到 $\text{K-D Tree}$ 里，像之前一样查询，注意相同的要一次性插入完，复杂度 $O(n\sqrt n)$，实测比 $\text{CDQ}$ 分治慢【七】。
例题七 [P5471 [NOI2019] 弹跳](/problem/P5471)
最短路，每一个点会向一个矩形内的点连一条权值相同的边。
$\text{K-D Tree}$ 既然是处理高维数据的利器，自然也有着优化建图的功能，这题一看就知道是裸的最短路板子，但由于边数过多，又与二维数点矩形查询相关，可以使用 $\text{K-D Tree}$ 的矩形查询操作。
有一定经验的同学一定知道，很多时候时间与空间并不均等，这道题更是略微卡常数，如果真的将边连起来，就不知道是 MLE 还是 TLE 了。
当将一个节点进行松弛时，将从他出发的每一个弹跳机在 $\text{K-D Tree}$ 上修改，最短路需要使用 Dijkstra 算法！由于瓶颈不在于堆，所以 SPFA 在这一年又死了一次。
代码很好写，只用了半小时：【八】
### Part3 树套 $\text{K-D Tree}
例题八 [P3769 [CH弱省胡策R2]TATT](/problem/P3769)
给定 $n\le5\times10^4$ 个点 $(a_i,b_i,c_i,d_i)$，求最长不下降子序列（要求每一维都不下降）。
不论是听说还是看题，都让我们知道这是一道四维偏序问题，许多人的做法都是 CDQ 套 CDQ 的 $O(n\log_2^3n)$ 和 三维 $\text{K-D Tree}$ 的 $O(n^\frac{5}{3})$，如果不是这题数据比较随机，一旦出题人把你卡满，就危险了，反正我不敢用三维 K-D Tree，于是想了一个神奇的时间 $O(n^\frac{3}{2})$，空间 $n\log_2n$ 的做法。
第一步是大家都要做的，通过将 $a$ 维排序将静态四维偏序转换成动态三维偏序，接下来，将编号按 $b$ 维排序，此处相同的不应去重，而应按编号继续比较；然后，使用树状数组套二维 $\text{K-D Tree}$，先建树，每次得到答案后在树上修改即可：【九】
空间复杂度很好理解，为什么时间复杂度是 $O(n^\frac{3}{2})$ 而不用再加一只 $\log$？
因为树状数组和 $\text{K-D Tree}$ 真的很般配！
设 $k=\log_2n$，则单次查询最坏时间为 $\sum\limits_{i\le k}\sqrt{2^i}\le2\sum\limits_{i\le\frac{k}{2}}2^i\le2^{\frac{k}{2}+2}=O(\sqrt{n})$，这和之前的二进制分组很相像。
例题九 [P4848 崂山白花蛇草水](/problem/P4848)
插入或修改二维数点权值，求矩形权值第 $k$ 大。
众所周知，~~也可能没什么人知道~~，权值线段树、平衡树、$\text{01trie}$ 在很多时候都是可以互相转化的，我就用了更好写，可能常数更小的 $\text{01trie}$。
容易发现，这道题可以二分，如果离线整体二分就可以了，然而出题人并没有允许离线！于是我们可以在外层套一棵权值线段树或 $\text{01trie}$，每个节点存维护了值域内所有“崂山白花蛇草水”坐标的 $\text{K-D Tree}$，每次树上二分，时间复杂度 $O(n\sqrt{n}\log_2C)$，空间复杂度 $O(n\log_2n\log_2C)$，以上 $C$ 均为值域：【十】
### Part4 后记
邻值查询的 $\text{K-D Tree}$ 是 $O(nq)$ 的，容易被特殊数据卡死，迟早是会像 $\text{SPFA}$ 一样退出舞台的。但矩形查询的优秀时空复杂度也令它值得我们传承、研究。本人深知这篇文章以及这个数据结构有许多不足，大家可以多提出改进意见，但不要像本人其他文章一样，出现以邻值查询复杂度错误为理由的抨击，$\text{OI}$ 路远，希望大家每天都有进步！
---
以下为题目代码：
【一】
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define P(x) (ll(x)*(x))
#define p(x) ((x)*(x))
const int N=4e5+5;
const ll T=0x3f3f3f3f3f3f3f3f;
char buf[1<<23],*p1,*p2,c;
#define gc (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<22,stdin),p1==p2))?EOF:*p1++
inline void read(int &x){
bool flag=x=0;while(!isdigit(c=gc))if(c=='-')flag=1;
do x=(x<<3)+(x<<1)+(c^'0');while(isdigit(c=gc));if(flag)x=-x;
}
ll ans=T;
int lc[N],rc[N],lx[N],ly[N],rx[N],ry[N],nowt,Id[N],n,Root;
struct Node{int x,y;}a[N];
inline bool cmpx(const int &x,const int &y){return a[x].x<a[y].x;}
inline bool cmpy(const int &x,const int &y){return a[x].y<a[y].y;}
#define Dis(a1,a2) (P(a[a1].x-a[a2].x)+P(a[a1].y-a[a2].y))
inline ll fac(int x){
if(!x)return T+50;ll res=0;
if(lx[x]>a[nowt].x)res+=P(lx[x]-a[nowt].x);
if(rx[x]<a[nowt].x)res+=P(a[nowt].x-rx[x]);
if(ly[x]>a[nowt].y)res+=P(ly[x]-a[nowt].y);
if(ry[x]<a[nowt].y)res+=P(a[nowt].y-ry[x]);
return res;
}
inline void Maintain(int x){
#define Max(a,b) (a>b?a:b)
#define Min(a,b) (a<b?a:b)
lx[x]=rx[x]=a[x].x;ly[x]=ry[x]=a[x].y;
if(lc[x])lx[x]=Min(lx[x],lx[lc[x]]),rx[x]=Max(rx[x],rx[lc[x]]),
ly[x]=Min(ly[x],ly[lc[x]]),ry[x]=Max(ry[x],ry[lc[x]]);
if(rc[x])lx[x]=Min(lx[x],lx[rc[x]]),rx[x]=Max(rx[x],rx[rc[x]]),
ly[x]=Min(ly[x],ly[rc[x]]),ry[x]=Max(ry[x],ry[rc[x]]);
#undef Max
#undef Min
}
int build(int l,int r,bool Tp){
if(r<l)return 0;int mid=l+((r-l)>>1),x;
if(Tp)nth_element(Id+l,Id+mid,Id+r+1,cmpx);
else nth_element(Id+l,Id+mid,Id+r+1,cmpy);x=Id[mid];
lc[x]=build(l,mid-1,Tp^1);rc[x]=build(mid+1,r,Tp^1);Maintain(x);
return x;
}
void asks(int x){
if(x!=nowt)ans=min(ans,Dis(x,nowt));
ll fl=fac(lc[x]),fr=fac(rc[x]);
if(fl<fr){if(fl<ans){asks(lc[x]);if(fr<ans)asks(rc[x]);}}
else{if(fr<ans)asks(rc[x]);if(fl<ans)asks(lc[x]);}
}
int main(){
int i;read(n);
for(i=1;i<=n;Id[i]=i,++i)read(a[i].x),read(a[i].y);
Root=build(1,n,0);
for(i=1;i<=n;++i)nowt=Id[i],asks(Root);
printf("%lld\n",ans);
return 0;
}
```
【二】
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define P(x) (ll(x)*(x))
#define p(x) ((x)*(x))
const int N=4e5+5;
const ll T=0x3f3f3f3f3f3f3f3f;
char buf[1<<23],*p1,*p2,c;
#define gc (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<22,stdin),p1==p2))?EOF:*p1++
inline void read(int &x){
bool flag=x=0;while(!isdigit(c=gc))if(c=='-')flag=1;
do x=(x<<3)+(x<<1)+(c^'0');while(isdigit(c=gc));if(flag)x=-x;
}
ll ans=T;
int lc[N],rc[N],lx[N],ly[N],rx[N],ry[N],nowt,Id[N],n,Root;
struct Node{int x,y;}a[N];
inline bool cmpx(const int &x,const int &y){return a[x].x<a[y].x;}
inline bool cmpy(const int &x,const int &y){return a[x].y<a[y].y;}
#define Dis(a1,a2) (P(a[a1].x-a[a2].x)+P(a[a1].y-a[a2].y))
inline ll fac(int x){
if(!x)return T+50;ll res=0;
if(lx[x]>a[nowt].x)res+=P(lx[x]-a[nowt].x);
if(rx[x]<a[nowt].x)res+=P(a[nowt].x-rx[x]);
if(ly[x]>a[nowt].y)res+=P(ly[x]-a[nowt].y);
if(ry[x]<a[nowt].y)res+=P(a[nowt].y-ry[x]);
return res;
}
inline void Maintain(int x){
#define Max(a,b) (a>b?a:b)
#define Min(a,b) (a<b?a:b)
lx[x]=rx[x]=a[x].x;ly[x]=ry[x]=a[x].y;
if(lc[x])lx[x]=Min(lx[x],lx[lc[x]]),rx[x]=Max(rx[x],rx[lc[x]]),
ly[x]=Min(ly[x],ly[lc[x]]),ry[x]=Max(ry[x],ry[lc[x]]);
if(rc[x])lx[x]=Min(lx[x],lx[rc[x]]),rx[x]=Max(rx[x],rx[rc[x]]),
ly[x]=Min(ly[x],ly[rc[x]]),ry[x]=Max(ry[x],ry[rc[x]]);
#undef Max
#undef Min
}
double px,py,fx,fy;
int build(int l,int r){
if(r<l)return 0;int mid=l+((r-l)>>1),x;px=py=fx=fy=0;
for(x=l;x<=r;++x)px+=a[Id[x]].x,py+=a[Id[x]].y;px/=r-l+1;py/=r-l+1;
for(x=l;x<=r;++x)fx+=p(px-a[Id[x]].x),fy+=p(py-a[Id[x]].y);
if(fx>fy)nth_element(Id+l,Id+mid,Id+r+1,cmpx);
else nth_element(Id+l,Id+mid,Id+r+1,cmpy);x=Id[mid];
lc[x]=build(l,mid-1);rc[x]=build(mid+1,r);Maintain(x);
return x;
}
void asks(int x){
if(x!=nowt)ans=min(ans,Dis(x,nowt));
ll fl=fac(lc[x]),fr=fac(rc[x]);
if(fl<fr){if(fl<ans){asks(lc[x]);if(fr<ans)asks(rc[x]);}}
else{if(fr<ans)asks(rc[x]);if(fl<ans)asks(lc[x]);}
}
int main(){
int i;read(n);
for(i=1;i<=n;Id[i]=i,++i)read(a[i].x),read(a[i].y);
Root=build(1,n);
for(i=1;i<=n;++i)nowt=Id[i],asks(Root);
printf("%lld\n",ans);
return 0;
}
```
【三】
```cpp
#include<bits/stdc++.h>
#define p2(x) ((x)*(x))
using namespace std;
const int N=1e5+5;
char buf[1<<23],*p1,*p2,c;
#define gc (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<22,stdin),p1==p2))?EOF:*p1++
inline int read(){
int an=0;while(!isdigit(c=gc));
do an=(an<<3)+(an<<1)+(c^'0');
while(isdigit(c=gc));return an;
}
typedef unsigned long long ll;
priority_queue<ll,vector<ll>,greater<ll> >Set;
struct Node{int x,y;}a[N];
inline bool cmpx(const Node &x,const Node &y){return x.x<y.x;}
inline bool cmpy(const Node &x,const Node &y){return x.y<y.y;}
inline ll dis(const int &x,const int &y){
return p2(ll(a[x].x-a[y].x))+p2(ll(a[x].y-a[y].y));
}
int lx[N],rx[N],ly[N],ry[N],lc[N],rc[N],n,k;
inline ll fac(int d,int x){
ll ax=max(a[x].x-lx[d],rx[d]-a[x].x);
ll ay=max(a[x].y-ly[d],ry[d]-a[x].y);
return p2(ax)+p2(ay);
}
inline void Maintain(int x){
lx[x]=rx[x]=a[x].x;ly[x]=ry[x]=a[x].y;
if(lc[x])lx[x]=min(lx[x],lx[lc[x]]),rx[x]=max(rx[x],rx[lc[x]]),
ly[x]=min(ly[x],ly[lc[x]]),ry[x]=max(ry[x],ry[lc[x]]);
if(rc[x])lx[x]=min(lx[x],lx[rc[x]]),rx[x]=max(rx[x],rx[rc[x]]),
ly[x]=min(ly[x],ly[rc[x]]),ry[x]=max(ry[x],ry[rc[x]]);
return;
}
int build(int l,int r){
if(r<l)return 0;int mid=l+((r-l)>>1),i;
if(l&1)nth_element(a+l,a+mid,a+r+1,cmpx);
else nth_element(a+l,a+mid,a+r+1,cmpy);
lc[mid]=build(l,mid-1);
rc[mid]=build(mid+1,r);
Maintain(mid);return mid;
}
inline void asks(int l,int r,int x){
if(r<l)return;int mid=l+((r-l)>>1);ll w=dis(mid,x);
if(mid!=x)if((w=dis(mid,x))>Set.top())Set.pop(),Set.push(w);
if(l==r)return;
ll fl=fac(lc[mid],x),fr=fac(rc[mid],x),Min=Set.top();
if(fl>Min&&fr>Min){
if(fl>=fr){asks(l,mid-1,x);if(fr>Set.top())asks(mid+1,r,x);}
else{asks(mid+1,r,x);if(fl>Set.top())asks(l,mid-1,x);}
}else if(fl>Min)asks(l,mid-1,x);
else if(fr>Min)asks(mid+1,r,x);
return;
}
int main(){
n=read();k=read()<<1;int i;
for(i=1;i<=k;++i)Set.push(0);
for(i=1;i<=n;++i)a[i]={read(),read()};
build(1,n);for(i=1;i<=n;++i)asks(1,n,i);
printf("%llu\n",Set.top());
return 0;
}
```
【四】
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5e4+4,M=1e6+6;
char buf[M+5],*p1,*p2,c;
#define gc (p1==p2&&(p2=(p1=buf)+fread(buf,1,M,stdin),p1==p2)?EOF:*p1++)
inline int read(){
int x,f=1;for(c=gc;c<48;c=gc)if(c=='-')f=-f;
for(x=0;c>47;x=x*10+(48^c),c=gc);return x*f;
}
ll lx[N],rx[N],ly[N],ry[N],mx[N],my[N],mm[N],sm[N],ans;
struct Node{int x,y,h;}a[N];
int n,Q,cmpT;
inline bool operator<(const Node &x,const Node &y){
return cmpT?x.x<y.x:x.y<y.y;
}
#define Max(a,b) if(a<b)a=b
#define Min(a,b) if(a>b)a=b
int build(int l,int r){
int x=l+r>>1,y;cmpT^=1;
nth_element(a+l,a+x,a+r+1);
lx[x]=rx[x]=mx[x]=a[x].x;
ly[x]=ry[x]=my[x]=a[x].y;
sm[x]=mm[x]=a[x].h;
if(l<x){
y=build(l,x-1);sm[x]+=sm[y];
Min(lx[x],lx[y]);Min(ly[x],ly[y]);
Max(rx[x],rx[y]);Max(ry[x],ry[y]);
}if(x<r){
y=build(x+1,r);sm[x]+=sm[y];
Min(lx[x],lx[y]);Min(ly[x],ly[y]);
Max(rx[x],rx[y]);Max(ry[x],ry[y]);
}return x;
}
void ask(int l,int r){
int x=l+r>>1;ll L,R,D,U;
L=lx[x]*a[0].x,R=rx[x]*a[0].x;
D=ly[x]*a[0].y,U=ry[x]*a[0].y;
if(L>R)L^=R^=L^=R;
if(D>U)D^=U^=D^=U;
if(L+D>=a[0].h)return;
if(R+U<a[0].h){ans+=sm[x];return;}
L=mx[x]*a[0].x+my[x]*a[0].y;
if(L<a[0].h)ans+=mm[x];
if(l<x)ask(l,x-1);
if(x<r)ask(x+1,r);
}
int main(){
n=read(),Q=read();int i;
for(i=1;i<=n;++i)a[i]={read(),read(),read()};
build(1,n);
while(Q--){
a[ans=0]={read(),read(),read()};
ask(1,n),printf("%lld\n",ans);
}return 0;
}
```
【五】
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=6e5+5,Tinf=0x3f3f3f3f;
char buf[1<<23],*p1,*p2,c;
#define gc (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<22,stdin),p1==p2))?EOF:*p1++
inline int read(){
int an=0,f=1;while(!isdigit(c=gc))if(c=='-')f=-f;
do an=(an<<3)+(an<<1)+(c^'0');while(isdigit(c=gc));
return an*f;
}
int stk[N],lc[N],rc[N],siz[N],t,nodt,Root,Nrb,n,m,ccnntt;
int lx[N],ly[N],rx[N],ry[N],mx[N],my[N],nowx,nowy,ans;
bool Tp[N],nowTp;
struct Node{int x,y;}a[N];
inline bool cmpx(const Node &x,const Node &y){return x.x<y.x;}
inline bool cmpy(const Node &x,const Node &y){return x.y<y.y;}
inline int Abs(const int &x){return x<0?-x:x;}
inline int New(int dx,int dy){
int x=stk[t--];lx[x]=rx[x]=mx[x]=dx;
ly[x]=ry[x]=my[x]=dy;siz[x]=1;return x;
}
inline void Maintain(int x,int k){
if(lc[x])lx[x]=min(lx[x],lx[lc[x]]),rx[x]=max(rx[x],rx[lc[x]]),
ly[x]=min(ly[x],ly[lc[x]]),ry[x]=max(ry[x],ry[lc[x]]),siz[x]+=siz[lc[x]];
if(rc[x])lx[x]=min(lx[x],lx[rc[x]]),rx[x]=max(rx[x],rx[rc[x]]),
ly[x]=min(ly[x],ly[rc[x]]),ry[x]=max(ry[x],ry[rc[x]]),siz[x]+=siz[rc[x]];
}
int build(int l,int r){
if(r<l)return 0;int mid=l+((r-l)>>1),x;
double px=0,py=0,fx=0,fy=0;
for(x=l;x<=r;++x)px+=a[x].x,py+=a[x].y;
px/=double(r-l+1);py/=double(r-l+1);
for(x=l;x<=r;++x)fx+=(px-a[x].x)*(px-a[x].x),fy+=(py-a[x].y)*(py-a[x].y);
bool Type=fx>fy;
if(Type)nth_element(a+l,a+mid,a+r+1,cmpx);
else nth_element(a+l,a+mid,a+r+1,cmpy);
Tp[x=New(a[mid].x,a[mid].y)]=Type;
lc[x]=build(l,mid-1);
rc[x]=build(mid+1,r);
Maintain(x,mid);return x;
}
inline int fac(int x){
if(!x)return Tinf;int res=0;
if(rx[x]<nowx)res+=nowx-rx[x];
if(lx[x]>nowx)res+=lx[x]-nowx;
if(ry[x]<nowy)res+=nowy-ry[x];
if(ly[x]>nowy)res+=ly[x]-nowy;
return res;
}
void asks(int x){
ans=min(ans,Abs(mx[x]-nowx)+Abs(my[x]-nowy));
int fl=fac(lc[x]),fr=fac(rc[x]);
if(fl<ans&&fr<ans){
if(fl<fr){asks(lc[x]);if(fr<ans)asks(rc[x]);}
else{asks(rc[x]);if(fl<ans)asks(lc[x]);}
}else{
if(fl<ans)asks(lc[x]);
if(fr<ans)asks(rc[x]);
}return;
}
void Ins(int x){
lx[x]=min(lx[x],nowx);rx[x]=max(rx[x],nowx);
ly[x]=min(ly[x],nowy);ry[x]=max(ry[x],nowy);++siz[x];
if((Tp[x]&&nowx>mx[x])||((!Tp[x])&&nowy>my[x])){
if(rc[x]){Ins(rc[x]);if(siz[rc[x]]>siz[lc[x]]*3)Nrb=x;}
else rc[x]=New(nowx,nowy);
}else{
if(lc[x]){Ins(lc[x]);if(siz[lc[x]]>siz[rc[x]]*3)Nrb=x;}
else lc[x]=New(nowx,nowy);
}return;
}
void GetNode(int x){
if(lc[x])GetNode(lc[x]);
a[++nodt]={mx[x],my[x]};
if(rc[x])GetNode(rc[x]);
stk[++t]=x;return;
}
int main(){
int i,opt;for(i=N-2;i;--i)stk[++t]=i;
n=read();m=read();for(i=1;i<=n;++i)a[++nodt]={read(),read()};
Root=build(1,nodt);
for(i=1;i<=m;++i){
opt=read();nowx=read();nowy=read();
if(opt==2){ans=Tinf;asks(Root);printf("%d\n",ans);}
else{
Nrb=0;Ins(Root);
if(Nrb){nodt=0;GetNode(Nrb);build(1,nodt);}
}
}
return 0;
}
```
【六】
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
char buf[1<<23],*p1,*p2,c;
#define gc (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<22,stdin),p1==p2))?EOF:*p1++
inline int read(){
int an=0,f=1;while(!isdigit(c=gc))if(c=='-')f=-f;
do an=an*10+c-'0';while(isdigit(c=gc));return an*f;
}
int mx[N],my[N],md[N],lx[N],ly[N],rx[N],ry[N],stk[N],t,Root;
int lc[N],rc[N],d[N],siz[N],Need_Rebuild,NodeTp,ans_data;
struct Node{int x,y,d;}a[N];
bool Tp[N],nowTp;
inline bool cmpx(const Node &x,const Node &y){return x.x<y.x;}
inline bool cmpy(const Node &x,const Node &y){return x.y<y.y;}
inline int New(int id){
int x=stk[t--];lx[x]=rx[x]=mx[x]=a[id].x;md[x]=d[x]=a[id].d;
ly[x]=ry[x]=my[x]=a[id].y;siz[x]=1;return x;
}
bool Ins(int &x){
if(x==0){Tp[x=New(0)]=nowTp^=1;return 1;}d[x]+=a[0].d;
if(mx[x]==a[0].x&&my[x]==a[0].y){md[x]+=a[0].d;return 0;}
lx[x]=min(lx[x],a[0].x);ly[x]=min(ly[x],a[0].y);
rx[x]=max(rx[x],a[0].x);ry[x]=max(ry[x],a[0].y);bool res;
if((Tp[x]&&a[0].x<mx[x])||((!Tp[x])&&a[0].y<my[x])){
if((res=Ins(lc[x]))&&siz[lc[x]]>siz[rc[x]]*3+3)Need_Rebuild=x;
}else{
if((res=Ins(rc[x]))&&siz[rc[x]]>siz[lc[x]]*3+3)Need_Rebuild=x;
}siz[x]+=res;return res;
}
inline void Maintain(int x){
if(lc[x])lx[x]=min(lx[x],lx[lc[x]]),ly[x]=min(ly[x],ly[lc[x]]),d[x]+=d[lc[x]],
rx[x]=max(rx[x],rx[lc[x]]),ry[x]=max(ry[x],ry[lc[x]]),siz[x]+=siz[lc[x]];
if(rc[x])lx[x]=min(lx[x],lx[rc[x]]),ly[x]=min(ly[x],ly[rc[x]]),d[x]+=d[rc[x]],
rx[x]=max(rx[x],rx[rc[x]]),ry[x]=max(ry[x],ry[rc[x]]),siz[x]+=siz[rc[x]];
}
void GetNode(const int &x){
if(lc[x])GetNode(lc[x]);
a[++NodeTp]={mx[x],my[x],md[x]};
if(rc[x])GetNode(rc[x]);
stk[++t]=x;return;
}
void asks(int x){
if(lx[x]>=lx[0]&&rx[x]<=rx[0]&&ly[x]>=ly[0]&&ry[x]<=ry[0]){ans_data+=d[x];return;}
if(lx[0]>rx[x]||rx[0]<lx[x]||ly[0]>ry[x]||ry[0]<ly[x])return;
if(mx[x]>=lx[0]&&mx[x]<=rx[0]&&my[x]>=ly[0]&&my[x]<=ry[0])ans_data+=md[x];
if(lc[x])asks(lc[x]);if(rc[x])asks(rc[x]);return;
}
double px,py,fx,fy;
#define P(x) ((x)*(x))
int build(int l,int r){
if(r<l)return 0;int mid=l+((r-l)>>1),x;px=py=fx=fy=0;
for(x=l;x<=r;++x)px+=a[x].x,py+=a[x].y;px/=r-l+1,py/=r-l+1;
for(x=l;x<=r;++x)fx+=P(px-a[x].x),fy+=P(py-a[x].y);
if(fx>fy)nth_element(a+l,a+mid,a+r+1,cmpx);
else nth_element(a+l,a+mid,a+r+1,cmpy);
Tp[x=New(mid)]=fx>fy;lc[x]=build(l,mid-1);
rc[x]=build(mid+1,r);Maintain(x);return x;
}
#undef P
int main(){
int opt=read();
for(opt=N-1;opt;--opt)stk[++t]=opt;
for(opt=read();opt!=3;opt=read())
if(opt==1){
a[0]={read()^ans_data,read()^ans_data,read()^ans_data};
Need_Rebuild=0;Ins(Root);if(Need_Rebuild){
NodeTp=0;GetNode(Need_Rebuild);build(1,NodeTp);
}
}else{
lx[0]=read()^ans_data,ly[0]=read()^ans_data;
rx[0]=read()^ans_data,ry[0]=read()^ans_data;
ans_data=0;asks(Root);printf("%d\n",ans_data);
}
return 0;
}
```
【七】
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
char buf[1<<23],*p1,*p2,c;
#define gc (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<22,stdin),p1==p2))?EOF:*p1++
inline int read(){
int an=0,f=1;while(!isdigit(c=gc))if(c=='-')f=-f;
do an=(an<<3)+(an<<1)+(c^'0');while(isdigit(c=gc));
return an*f;
}
int n,k,ans[N],Id[N],lc[N],rc[N],siz[N],stk[N],t,Nans;
int lx[N],rx[N],ly[N],ry[N],mx[N],my[N],Nreb,NodeTp,Root;
bool Tp[N],cmpTp;
struct Node{int x,y;}a[N];
inline bool CmpInt(const int &x,const int &y){
return cmpTp?a[x].x<a[y].x:a[x].y<a[y].y;
}
struct Dat{int x,y,z;}dt[N];
inline bool operator<(const Dat &x,const Dat &y){
return x.z<y.z;
}
inline int New(const int &_Nd){
int x=stk[t--];lx[x]=rx[x]=mx[x]=a[_Nd].x;
ly[x]=ry[x]=my[x]=a[_Nd].y;siz[x]=1;
Tp[x]=cmpTp;cmpTp^=1;return x;
}
#define Max(a,b) if(a<b)a=b;
#define Min(a,b) if(a>b)a=b;
inline int Maintain(const int &x){
if(lc[x]){
Min(lx[x],lx[lc[x]]);Min(ly[x],ly[lc[x]]);
Max(rx[x],rx[lc[x]]);Max(ry[x],ry[lc[x]]);
siz[x]+=siz[lc[x]];
}if(rc[x]){
Min(lx[x],lx[rc[x]]);Min(ly[x],ly[rc[x]]);
Max(rx[x],rx[rc[x]]);Max(ry[x],ry[rc[x]]);
siz[x]+=siz[rc[x]];
}return x;
}
double px,py,fx,fy;
int build(int l,int r){
if(r<l)return 0;int x,mid=l+((r-l)>>1);
px=py=fx=fy=0;
for(x=l;x<=r;++x)px+=a[Id[x]].x,py+=a[Id[x]].y;
px/=r-l+1;py/=r-l+1;
for(x=l;x<=r;++x){
fx+=(px-a[Id[x]].x)*(px-a[Id[x]].x);
fy+=(py-a[Id[x]].y)*(py-a[Id[x]].y);
}cmpTp=fx>fy;
nth_element(Id+l,Id+mid,Id+r+1,CmpInt);
x=New(Id[mid]);
lc[x]=build(l,mid-1),rc[x]=build(mid+1,r);
return Maintain(x);
}
void Ins(int &x){
if(x==0){x=New(0);return;}++siz[x];
Min(lx[x],a[0].x);Min(ly[x],a[0].y);
Max(rx[x],a[0].x);Max(ry[x],a[0].y);
if((Tp[x]&&a[0].x<mx[x])||((!Tp[x])&&a[0].y<my[x])){
Ins(lc[x]);if(siz[lc[x]]>siz[rc[x]]*3+3)Nreb=x;
}else{
Ins(rc[x]);if(siz[rc[x]]>siz[lc[x]]*3+3)Nreb=x;
}return;
}
void GetNode(const int &x){
if(lc[x])GetNode(lc[x]);a[++NodeTp]={mx[x],my[x]};
if(rc[x])GetNode(rc[x]);stk[++t]=x;return;
}
void asks(int x){
if(rx[x]<=a[0].x&&ry[x]<=a[0].y){Nans+=siz[x];return;}
if(lx[x]>a[0].x||ly[x]>a[0].y)return;
Nans+=mx[x]<=a[0].x&&my[x]<=a[0].y;
if(lc[x])asks(lc[x]);if(rc[x])asks(rc[x]);return;
}
int main(){
n=read();k=read();int i,p=1;
for(i=1;i<=n;++i)dt[i]={read(),read(),read()};
stable_sort(dt+1,dt+n+1);
for(i=n<<1;i;--i)stk[++t]=i;
for(i=1;i<=n;++i){
while(p<=n&&dt[p].z<=dt[i].z){
a[0]={dt[p].x,dt[p].y},Nreb=0,++p,Ins(Root);
if(Nreb){
NodeTp=0,GetNode(Nreb);
for(k=1;k<=NodeTp;++k)Id[k]=k;
build(1,NodeTp);
}
}
Nans=0;a[0]={dt[i].x,dt[i].y};
asks(Root);++ans[Nans];
}
for(i=1;i<=n;++i)
printf("%d\n",ans[i]);
return 0;
}
```
【八】
```cpp
#include<bits/stdc++.h>
#include<ext/pb_ds/priority_queue.hpp>
#define ns __gnu_pbds
using namespace std;
const int T=70004,N=150005;
char buf[N+5],*p1,*p2,c;
#define gc (p1==p2&&(p2=(p1=buf)+fread(buf,1,N,stdin),p1==p2)?EOF:*p1++)
inline int read(){
int x,f=1;for(c=gc;c<'0'||c>'9';c=gc)if(c=='-')f=-f;
for(x=0;c>='0'&&c<='9';x=x*10+(48^c),c=gc);
return x*f;
}
struct Dat{int w,lx,rx,ly,ry;}g[N];
vector<int>lk[T];
int n,m,lx[N],rx[N],ly[N],ry[N],mx[N],my[N],lc[N],rc[N],ax[N],ay[N],a[N],lt[N],rt[N];
bool cmptp;
inline bool cmpI(const int &x,const int &y){
return cmptp?ay[x]<ay[y]:ax[x]<ax[y];
}
typedef long long ll;
typedef pair<ll,int>Tp;
long long d[T],ds[T];
ns::priority_queue<Tp,greater<Tp>,ns::pairing_heap_tag>pq;
double px,py,fx,fy;
bitset<N>vs;
int cnt;
int build(int l,int r){
int x=l+r>>1,i;ds[x]=1e15;lt[x]=l,rt[x]=r;
px=py=0;for(i=l;i<=r;++i)px+=ax[a[i]],py+=ay[a[i]];
fx=fy=0;for(i=l;i<=r;++i)fx+=(px-ax[a[i]])*(px-ax[a[i]]),fy+=(py-ay[a[i]])*(py-ay[a[i]]);
cmptp=fx<fy,nth_element(a+l,a+x,a+r+1,cmpI);
lx[x]=rx[x]=mx[x]=ax[a[x]],ly[x]=ry[x]=my[x]=ay[a[x]];
if(l<x)lc[x]=build(l,x-1),lx[x]=min(lx[x],lx[lc[x]]),rx[x]=max(rx[x],rx[lc[x]]),
ly[x]=min(ly[x],ly[lc[x]]),ry[x]=max(ry[x],ry[lc[x]]);
if(x<r)rc[x]=build(x+1,r),lx[x]=min(lx[x],lx[rc[x]]),rx[x]=max(rx[x],rx[rc[x]]),
ly[x]=min(ly[x],ly[rc[x]]),ry[x]=max(ry[x],ry[rc[x]]);return x;
}
void ask(int l,int r){
int x=l+r>>1;if(ds[x]<d[0])return;
if(lx[x]>=g[0].lx&&rx[x]<=g[0].rx&&ly[x]>=g[0].ly&&ry[x]<=g[0].ry){
ds[x]=d[0];pq.push(Tp(ds[x],x+n));return;
}if(d[a[x]]>d[0]&&mx[x]>=g[0].lx&&mx[x]<=g[0].rx&&my[x]>=g[0].ly&&my[x]<=g[0].ry)
d[a[x]]=d[0],pq.push(Tp(d[a[x]],a[x]));
if(lx[x]>g[0].rx||rx[x]<g[0].lx||ly[x]>g[0].ry||ry[x]<g[0].ly)return;
if(l<x)ask(l,x-1);if(x<r)ask(x+1,r);return;
}
int main(){
n=read(),m=read();read(),read();int i,x;
for(i=1;i<=n;++i)ax[i]=read(),ay[i]=read(),a[i]=i;
for(i=1;i<=m;++i){
x=read();g[i]={read(),read(),read(),read(),read()};
lk[x].push_back(i);
}build(1,n);
for(i=2;i<=n;++i)d[i]=1e15;
pq.push(Tp(d[1],1));
while(!pq.empty()){
x=pq.top().second,pq.pop();
if(vs[x])continue;
else vs[x]=1;
if(x>n){
for(x-=n,i=lt[x];i<=rt[x];++i)
if(d[a[i]]>ds[x])pq.push(Tp(d[a[i]]=ds[x],a[i]));
}else{
for(int y:lk[x])
g[0]=g[y],d[0]=d[x]+g[y].w,ask(1,n);
}
}for(i=2;i<=n;++i)printf("%lld\n",d[i]);
return 0;
}
```
【九】
```cpp
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=5e4+4,M=1e6+6;
char buf[M+5],*p1,*p2,c;
#define gc (p1==p2&&(p2=(p1=buf)+fread(buf,1,M,stdin),p1==p2)?EOF:*p1++)
inline int read(){
int x;for(c=gc;c<'!';c=gc);
for(x=0;c>'!';x=x*10+(48^c),c=gc);
return x;
}
int lx[M],rx[M],ly[M],ry[M],mx[M],my[M],xa[M],ma[M];
int t[M][2],cnt,nrb,nt,lz[M];
int cnt1,cnt2;
struct Tp{int x,y;}a[N];
char now;
inline bool operator<(const Tp &x,const Tp &y){
return now?x.x<y.x:x.y<y.y;
}
#define ls t[x][0]
#define rs t[x][1]
#define Max(x,y) if(x<y)x=y
#define Min(x,y) if(x>y)x=y
int build(int l,int r){
int x=++cnt,md=l+r>>1,i;now^=1;
nth_element(a+l,a+md,a+r+1);
lx[x]=rx[x]=mx[x]=a[md].x;
ly[x]=ry[x]=my[x]=a[md].y;
if(l<md){
ls=build(l,md-1);Min(lx[x],lx[ls]);
Min(ly[x],ly[ls]);Max(rx[x],rx[ls]);
Max(ry[x],ry[ls]);
}
if(md<r){
rs=build(md+1,r);Min(lx[x],lx[rs]);
Min(ly[x],ly[rs]);Max(rx[x],rx[rs]);
Max(ry[x],ry[rs]);
}
return x;
}
inline bool ck(int x){
return x&&lx[x]<=mx[0]&&ly[x]<=my[0]&&xa[x]>ma[0];
}
inline bool ck2(int x){
return x&&lx[x]<=mx[0]&&rx[x]>=mx[0]&&ly[x]<=my[0]&&ry[x]>=my[0];
}
inline void pd(int x){
Max(ma[x],lz[x]);
if(ls){Max(lz[ls],lz[x]);Max(xa[ls],lz[ls]);}
if(rs){Max(lz[rs],lz[x]);Max(xa[rs],lz[rs]);}
lz[x]=0;
}
void ask(int x){
if(lz[x])pd(x);
if(rx[x]<=mx[0]&&ry[x]<=my[0]){
Max(ma[0],xa[x]);return;
}if(mx[x]<=mx[0]&&my[x]<=my[0])
Max(ma[0],ma[x]);
if(ck(ls))ask(ls);
if(ck(rs))ask(rs);
}
void cg(int x){
if(lx[x]==mx[0]&&rx[x]==mx[0]&&ly[x]==my[0]&&ry[x]==my[0]){
Max(lz[x],ma[0]);Max(xa[x],lz[x]);
}else{
if(mx[x]==mx[0]&&my[x]==my[0]){
Max(ma[x],ma[0]);Max(xa[x],ma[x]);
}if(ck2(ls)){cg(ls);Max(xa[x],xa[ls]);}
if(ck2(rs)){cg(rs);Max(xa[x],xa[rs]);}
}
}
struct kdt{
int rt;
inline int qry(int x,int y){
mx[0]=x,my[0]=y,ma[0]=0;
if(ck(rt))ask(rt);
return ma[0];
}
inline void add(int x,int y,int d){
mx[0]=x,my[0]=y,ma[0]=d;
if(ck2(rt))cg(rt);
}
}tr[N];
int n,bI[N],rk[N],mt,ans[N];
struct Dat{int a[4];}d[N];
int main(){
int i,j,x;
for(n=read(),i=1;i<=n;++i)
d[bI[i]=i]={{read(),read(),read(),read()}};
stable_sort(d+1,d+n+1,[&](Dat x,Dat y){
for(i=0;i<4;++i)
if(x.a[i]!=y.a[i])return x.a[i]<y.a[i];
return false;
});
stable_sort(bI+1,bI+n+1,[&](int x,int y){
return d[x].a[1]==d[y].a[1]?x<y:d[x].a[1]<d[y].a[1];
});
for(i=1;i<=n;++i)rk[bI[i]]=i;
for(i=1;i<=n;++i){
nt=i&-i;
for(j=1;j<=nt;++j){
x=bI[i-j+1];
a[j]={d[x].a[2],d[x].a[3]};
}
tr[i].rt=build(1,nt);
}
for(i=1;i<=n;++i){
for(j=rk[i];j;j-=j&-j)
ans[i]=max(ans[i],tr[j].qry(d[i].a[2],d[i].a[3]));
ans[0]=max(ans[0],++ans[i]);
for(j=rk[i];j<=n;j+=j&-j)
tr[j].add(d[i].a[2],d[i].a[3],ans[i]);
}
printf("%d\n",ans[0]);
return 0;
}
```
【十】
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=4e6+6;
char buf[N+5],*p1,*p2,c;
#define gc (p1==p2&&(p2=(p1=buf)+fread(buf,1,N,stdin),p1==p2)?EOF:*p1++)
inline int read(){
int an=0,f=1;while(!isdigit(c=gc))if(c=='-')f=-f;
do an=an*10+(48^c);while(isdigit(c=gc));return an*f;
}
namespace tree_2d{
int lx[N],rx[N],mx[N],sz[N],pt[N],bt,lc[N],rc[N];
int ly[N],ry[N],my[N],stk[N],t,nrb,cnt;
struct rbtp{int x,y;}a[N];
#define Mn(a,b) if(a>b)a=b
#define Mx(a,b) if(a<b)a=b
void Ins(int &x,int dep=0){
if(!x){sz[x=++cnt]=1;lx[x]=rx[x]=mx[x]=mx[0];ly[x]=ry[x]=my[x]=my[0];pt[x]=pt[0]^=1;return;}
Mn(lx[x],mx[0]);Mn(ly[x],my[0]);
Mx(rx[x],mx[0]);Mx(ry[x],my[0]);++sz[x];
if((pt[x]&&mx[0]<mx[x])||(!pt[x]&&my[0]<my[x])){
Ins(lc[x]);if(sz[lc[x]]>sz[rc[x]]*3+2)nrb=x;
}else{
Ins(rc[x]);if(sz[rc[x]]>sz[lc[x]]*3+2)nrb=x;
}return;
}
int build(int l=1,int r=bt){
int md=l+r>>1,x;pt[x=stk[t--]]=pt[0]^=1;
nth_element(a+l,a+md,a+r+1,[&](rbtp g,rbtp h){return pt[x]?g.x<h.x:g.y<h.y;});
lx[x]=rx[x]=mx[x]=a[md].x,ly[x]=ry[x]=my[x]=a[md].y,sz[x]=1;
if(l<md){
lc[x]=build(l,md-1);Mx(rx[x],rx[lc[x]]);Mx(ry[x],ry[lc[x]]);
Mn(lx[x],lx[lc[x]]);Mn(ly[x],ly[lc[x]]);sz[x]+=sz[lc[x]];
}else lc[x]=0;
if(md<r){
rc[x]=build(md+1,r);Mx(rx[x],rx[rc[x]]);Mx(ry[x],ry[rc[x]]);
Mn(lx[x],lx[rc[x]]);Mn(ly[x],ly[rc[x]]);sz[x]+=sz[rc[x]];
}else rc[x]=0;
return x;
}
void get(int x=nrb){
if(lc[x])get(lc[x]);a[++bt]={mx[x],my[x]};
if(rc[x])get(rc[x]);stk[++t]=x;
}
inline bool ck(int x){
return x&&lx[x]<=rx[0]&&rx[x]>=lx[0]&&ly[x]<=ry[0]&&ry[x]>=ly[0];
}
void ask(int x){
if(lx[x]>=lx[0]&&rx[x]<=rx[0]&&ly[x]>=ly[0]&&ry[x]<=ry[0]){
nrb+=sz[x];return;
}if(mx[x]>=lx[0]&&mx[x]<=rx[0]&&my[x]>=ly[0]&&my[x]<=ry[0])++nrb;
if(ck(lc[x]))ask(lc[x]);if(ck(rc[x]))ask(rc[x]);
}
struct KDT{
int rt;
inline void insert(int x,int y){
mx[0]=x,my[0]=y,nrb=0,Ins(rt);
if(nrb)bt=0,get(),build();
}
inline int order(int Lx,int Ly,int Rx,int Ry){
lx[0]=Lx,ly[0]=Ly,rx[0]=Rx,ry[0]=Ry;
nrb=0;if(ck(rt))ask(rt);
return nrb;
}
}tre[N];
};
using tree_2d::tre;
namespace trie_01{
int t[N][2],val,cnt,Lx,Ly,Rx,Ry;
void Ins(int &x,int w=31){
if(!x)x=++cnt;tre[x].insert(Lx,Ly);
if(w--)Ins(t[x][(val>>w)&1],w);
}
int gvl(int x,int rk){
int w=31,res=0,k;
while(w--){
k=tre[t[x][1]].order(Lx,Ly,Rx,Ry);
if(rk<=k)x=t[x][1],res|=1<<w;
else rk-=k,x=t[x][0];
}return res;
}
struct Trie{
int rt;
void insert(int x,int y,int vl){
Lx=x,Ly=y,val=vl,Ins(rt);
}
int getval(int lx,int ly,int rx,int ry,int rk){
Lx=lx,Ly=ly,Rx=rx,Ry=ry;
return gvl(rt,rk);
}
}tr;
};
using trie_01::tr;
int T,las;
int main(){
read(),T=read();int lx,ly,rx,ry;
while(T--)
if(read()&1){
lx=read()^las,ly=read()^las,rx=read()^las;
tr.insert(lx,ly,rx);
}else{
lx=read()^las,ly=read()^las,rx=read()^las,ry=read()^las,las^=read();
las=tr.getval(lx,ly,rx,ry,las);
if(las)printf("%d\n",las);
else puts("NAIVE!ORZzyz.");
}
return 0;
}
```