这一篇和前两篇目的不太一样，这里更加偏向于一些好玩的神奇科技
part1 K-D tree
众所周知ben喜欢分块，但是分块不能(难以)处理多维问题
ben不喜欢树套树，但是树套树可以
所以ben决定学 KDT从而减少学树套树(
kdt最大的优势在于对脑子需求小，只需要你能码
首先我们考虑kdt是什么
它是一棵二叉排序树，每一个节点管辖一个(超)矩形，什么叫超矩形?就是高维的"矩形"
构造
说的俗气一点，就是建树。我们希望这棵树尽可能在根号以下复杂度完成正常操作(否则跑不跑得过暴力都不好说)
参考平衡树，我们希望树高在对数级别
首先，我们需要保证，节点 \(u\) 的儿子所管辖的所有点都在 \(u\) 管辖矩形内
通常我们应对的都是二维三维问题，以二维为例
需要满足要求，最好的办法就是用一条横平竖直的线分割 \(u\) 的矩形，分别分给左右儿子
具体构造如下:
-
挑选一个维度，选择与该维度正交的超平面分割当前区域。对于二维就是一线分面
-
不妨假设若干点中，我们正在对其 \(x\) 作为标准划分。处于均匀的目的，不妨选择以点的 \(x\) 坐标中位数作为标准
-
继续分治下去，选择不同维度
其实是非常类似于划分树的
不妨考虑如何决定分割维度
两种做法是:
-
轮换分割:比如先 \(x\) 后 \(y\) 再 \(z\)
-
方差划分:哪一维方差大按哪一维
本文全程使用轮换因为好写，实际据说方差快一些，但是反正骗分干嘛写难写的啊
寻找中位数使用 nth_element 可以线性，可以算出总复杂度nlong，满足我们需求:
区间查询问题（RQ）
类似于线段树的思想，查询一个矩形 \(R\) 可以分为三类点:
-
无交，自然与答案无关
-
被包含，自然直接计入答案结束
-
部分交集
显然我们类似于线段树，一直经过第三类点，然后到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