这一篇和前两篇目的不太一样，这里更加偏向于一些好玩的神奇科技

part1 K-D tree

众所周知ben喜欢分块，但是分块不能(难以)处理多维问题

ben不喜欢树套树，但是树套树可以

所以ben决定学 KDT从而减少学树套树(

kdt最大的优势在于对脑子需求小，只需要你能码

首先我们考虑kdt是什么

它是一棵二叉排序树，每一个节点管辖一个(超)矩形，什么叫超矩形?就是高维的"矩形"

构造

说的俗气一点，就是建树。我们希望这棵树尽可能在根号以下复杂度完成正常操作(否则跑不跑得过暴力都不好说)

参考平衡树，我们希望树高在对数级别

首先，我们需要保证，节点 \(u\) 的儿子所管辖的所有点都在 \(u\) 管辖矩形内

通常我们应对的都是二维三维问题，以二维为例

需要满足要求，最好的办法就是用一条横平竖直的线分割 \(u\) 的矩形，分别分给左右儿子

具体构造如下:

• 挑选一个维度，选择与该维度正交的超平面分割当前区域。对于二维就是一线分面

• 不妨假设若干点中，我们正在对其 \(x\) 作为标准划分。处于均匀的目的，不妨选择以点的 \(x\) 坐标中位数作为标准

• 继续分治下去，选择不同维度

其实是非常类似于划分树的

不妨考虑如何决定分割维度

两种做法是:

• 轮换分割:比如先 \(x\) 后 \(y\) 再 \(z\)

• 方差划分:哪一维方差大按哪一维

本文全程使用轮换因为好写，实际据说方差快一些，但是反正骗分干嘛写难写的啊

寻找中位数使用 nth_element 可以线性，可以算出总复杂度nlong，满足我们需求:

区间查询问题（RQ）

类似于线段树的思想，查询一个矩形 \(R\) 可以分为三类点:

1. 无交，自然与答案无关

2. 被包含，自然直接计入答案结束

3. 部分交集

显然我们类似于线段树，一直经过第三类点，然后到12类为止

并且我们可以考虑到12类的子树内肯定不会有3类点，所以复杂度直接和3类点数量有关

对于每个矩形的边，考虑其穿过的节点个数

处于轮换，相邻两次必定是分别划分 \(x,y\)

从点数上来说，划分出的四个区域中每个'大小' 都是原先四分之一

设 \(T(n)\) 为大小为 \(n\) 的kdt中过区域数，则 \(T(n)=2T(n/4)+O(1)=O(\sqrt n)\)

复杂度得以保障

一个细节地方在于，由于划分的矩形在边界是有交的，所以一条直线可能经过了超过两个节点，那我们的分析就是错误的...吗?

实际上，递归向儿子，线总在一侧，不影响复杂度分析

值得一提，在 \(k\) 维空间里经过个数是 \(O(n^{1-\frac{1}{k}})\)

具体举个例子:Shooting Gallery

原先题意中给出的用射击点匹配矩形(靶子)很不聪明，难以实现

反过来考虑，让每个矩形去匹配自己对应射击点

先按高度排个序

对于射击点建立一棵 kdt，维护子树编号最小未被匹配而删除的射击点，RQ之后单点删除被匹配点即可

给出实现:

#include<bits/stdc++.h>
using namespace std;
int n;
const int N=1600005;
#define ls (rt<<1)
#define rs (rt<<1|1)
struct node{
    int xl,yl,xr,yr,p;
}a[N<<2];

struct point{
    int x,y,p;
}p[N];

struct squ{
    int xl,xr,yl,yr,p,h;
}s[N];

int m;

bool cx(point A,point B){return A.x<B.x;}
bool cy(point A,point B){return A.y<B.y;}
bool yzy(squ A,squ B){
    return A.h<B.h;
}

int ans[N];

void pushup(int rt){
    a[rt].p=min(a[ls].p,a[rs].p);
    a[rt].xl=min(a[ls].xl,a[rs].xl);
    a[rt].yl=min(a[ls].yl,a[rs].yl);
    a[rt].xr=max(a[ls].xr,a[rs].xr);
    a[rt].yr=max(a[ls].yr,a[rs].yr);
}

void build(int l,int r,int rt,bool D){
    if(l==r){
        a[rt].xl=a[rt].xr=p[l].x;
        a[rt].yl=a[rt].yr=p[l].y;
        a[rt].p=p[l].p;
        return ;
    }
    int mid=(l+r)>>1;
    nth_element(p+l,p+mid,p+r+1,D?cx:cy);
    build(l,mid,ls,!D);
    build(mid+1,r,rs,!D);
    pushup(rt);
}
int to;
void upd(int l=1,int r=n,int rt=1){
    if(l==r){
        a[rt].p=n+1;return;
    }
    int mid=(l+r)>>1;
    if(to<=mid) upd(l,mid,ls);
    else upd(mid+1,r,rs);
    a[rt].p=min(a[ls].p,a[rs].p);
}

node wt;
int tp[N];

void query(int rt=1){
    if(a[rt].p>=wt.p or wt.xr<a[rt].xl or a[rt].xr<wt.xl or wt.yr<a[rt].yl or wt.yl>a[rt].yr){
        return;
    }
    if(wt.xl<=a[rt].xl and a[rt].xr<=wt.xr and wt.yl<=a[rt].yl and a[rt].yr<=wt.yr){
        wt.p=min(wt.p,a[rt].p);
        return;
    }
    if(a[ls].p<a[rs].p){
        query(ls),query(rs);
    }
    else query(rs),query(ls);
}

int main(){
    cin>>m;
    for(int i=1;i<=m;i++){
        cin>>s[i].xl>>s[i].xr>>s[i].yl>>s[i].yr>>s[i].h;
        s[i].p=i;
    }
    sort(s+1,s+m+1,yzy);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>p[i].x>>p[i].y;p[i].p=i;
    }
    build(1,n,1,1);
    for(int i=1;i<=n;i++) tp[p[i].p]=i;
    for(int i=1;i<=m;i++){
        wt=(node){s[i].xl,s[i].yl,s[i].xr,s[i].yr,n+1};
        query();
        if(wt.p==n+1) continue;//cout<<i<<endl;
        ans[wt.p]=s[i].p;
        to=tp[wt.p];
        upd();
    }
    for(int i=1;i<=n;i++) cout<<ans[i]<<"\n";
}

part2 珂朵莉树(ODT)

to be upd