K-D Tree，处理高维数据的利器

也许有些同学还不了解 $\text{K-D Tree}$ 这种数据结构，这是一种基于暴力优化的“玄学”数据结构，“D”是维度的意思，“K”是维度常数。

$\text{K-D Tree}$ 的原理是基于线段树的，即用一个节点来管理一个矩形，举个例子：

$(1,2),(2,6),(5,3),(3,5),(4,4)$ 这五个点可以构建这样一颗 $\text{K-D Tree}$：
![](https://cdn.luogu.com.cn/upload/image_hosting/4u2rpmhs.png)

每个节点需要记下每一个维度的极值用来剪枝，例如查询第一维的范围是 $[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 邻值查询
$\text{K-D Tree}$ 在二维邻值查询的表现十分优秀，在随机数据下复杂度约为 $O((n+q)\log_2n)$，但还是最坏 $O(nq)$ 的，至今没有人在正式比赛中卡它。

例题一 [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}$
$\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;
}
```

正在渲染内容...