申请加入跑不满算法协会。
用于维护多维信息的 Unleafy Tree。
1 建树
每个节点维护一个矩阵的信息，具体的，需要记录矩阵内的横纵坐标最值。
建树时对当前点的矩阵横着竖着轮流切，中间的点作为该节点的权值，对于切下来的矩阵接着递归建树。
int cnt=0;
struct{int ls,rs,v[2],mn[2],mx[2];
}tr[200200];
#define mid ((l+r)>>1)
#define ls(x) tr[x].ls
#define rs(x) tr[x].rs
#define v(x,p) tr[x].v[p]
#define mn(x,p) tr[x].mn[p]
#define mx(x,p) tr[x].mx[p]
void up(int id){for(int i=0;i<2;i++){mn(id,i)=mx(id,i)=v(id,i);if(ls(id)){mn(id,i)=min(mn(id,i),mn(ls(id),i));mx(id,i)=max(mx(id,i),mx(ls(id),i));}if(rs(id)){mn(id,i)=min(mn(id,i),mn(rs(id),i));mx(id,i)=max(mx(id,i),mx(rs(id),i));}}
}
void build(int &id,int l,int r,int fl){if(l>r){id=0;return;}nth_element(a+l,a+mid,a+1+r,[fl](Murasame x,Murasame y){return x.v[fl]<y.v[fl];});id=++cnt;v(id,0)=a[mid].v[0],v(id,1)=a[mid].v[1];build(ls(id),l,mid-1,fl^1);build(rs(id),mid+1,r,fl^1);up(id);
}
2 邻域查询
邻域查询指查询最近/远点。
这是 \(O(n)\) 的，但是很多题不卡能草过一坨点，接下来以查询最远点为例。
考虑如果一个节点矩阵里查询点的最远距离也比答案要小，那么就不需要递归该节点。
设计一个加权函数表示节点矩阵里查询点的最远距离，递归时优先递归加权值更大的子树。
想不到魔怔话于是用这句话代替。
//ans2 为当前的答案。
int fmax(int id,int x,int y){int ans=0;ans+=max(abs(x-mn(id,0)),abs(x-mx(id,0)));ans+=max(abs(y-mx(id,1)),abs(y-mn(id,1)));return ans;
}
void qmax(int id,int x,int y){if(!id) return;ans2=max(ans2,abs(v(id,0)-x)+abs(v(id,1)-y));int vl=-2e9,vr=-2e9;if(ls(id)) vl=fmax(ls(id),x,y);if(rs(id)) vr=fmax(rs(id),x,y);if(vl>vr){if(vl>ans2) qmax(ls(id),x,y);if(vr>ans2) qmax(rs(id),x,y);} else{if(vr>ans2) qmax(rs(id),x,y);if(vl>ans2) qmax(ls(id),x,y);}
}
3 矩阵查询
Q：丛雨和 0d00 的共同点？。
像线段树一样，完全被查询区间包含就返回整个矩阵，相离就返回滚木，否则接着往下递归。
有精细证明该操作复杂度为单次 \(O(n^{1-\frac{1}{k}})\) 的，其中 \(k\) 为维数，但该证明需要主定理我不会😅。
int query(int id,int x1,int y1,int x2,int y2){if(!id) return 0;if(x1<=mn(id,0)&&y1<=mn(id,1)&&x2>=mx(id,0)&&y2>=mx(id,1)) return sz(id);//被完全包含if(x1> mx(id,0)||y1> mx(id,1)||x2< mn(id,0)||y2< mn(id,1)) return 0;//相离int fl=(x1<=v(id,0)&&y1<=v(id,1)&&x2>=v(id,0)&&y2>=v(id,1));//自身是否在查询矩阵内return query(ls(id),x1,y1,x2,y2)+query(rs(id),x1,y1,x2,y2)+fl;
}
4 查询一次函数下/上侧信息
丛雨并没有重力所以叫将臣起床施加的压力是来自……？。
照着矩阵查询的样子瞎写写就好了，复杂度伪的别管。
bool check(int x,int y,double k,double b,bool fl){//点是否在上/下侧return fl?(y>x*k+b):(y<x*k+b);
}
bool checkN(int id,double k,double b,bool fl){//矩阵是否完全不在上/下侧if(check(mn(id,0),mn(id,1),k,b,fl)) return 0;if(check(mx(id,0),mn(id,1),k,b,fl)) return 0;if(check(mn(id,0),mx(id,1),k,b,fl)) return 0;if(check(mx(id,0),mx(id,1),k,b,fl)) return 0;return 1;
}
bool checkA(int id,double k,double b,bool fl){//矩阵是否完全在上/下侧if(!check(mn(id,0),mn(id,1),k,b,fl)) return 0;if(!check(mx(id,0),mn(id,1),k,b,fl)) return 0;if(!check(mn(id,0),mx(id,1),k,b,fl)) return 0;if(!check(mx(id,0),mx(id,1),k,b,fl)) return 0;return 1;
}
int que(int id,double k,double b,bool fl){if(!id) return 0;if(checkN(id,k,b,fl)) return 0;if(checkA(id,k,b,fl)) return sum(id);return que(ls(id),k,b,fl)+que(rs(id),k,b,fl)+val(id)*check(v(id,0),v(id,1),k,b,fl);//记得加自身贡献
}
5 求第 k 远点
受不了了太魔怔了不写了。
拿个优先队列存下前 k 远就行了，估价函数直接抄最远的就行了，如果权值比当前第 k 远小就不进行递归。
提前往优先队列里放 k 个 -1 能省掉一些细节。
int fmax(int id,int x,int y){int ans=0;ans+=max(abs(x-mn(id,0)),abs(x-mx(id,0)))*max(abs(x-mn(id,0)),abs(x-mx(id,0)));ans+=max(abs(y-mx(id,1)),abs(y-mn(id,1)))*max(abs(y-mx(id,1)),abs(y-mn(id,1)));return ans;
}
void qmax(int id,int x,int y){if(!id) return;q.push({dis(v(id,0),v(id,1),x,y),p(id)});q.pop();int vl=-2e9,vr=-2e9,ans=q.top().val;if(ls(id)) vl=fmax(ls(id),x,y);if(rs(id)) vr=fmax(rs(id),x,y);if(vl>vr){if(vl>=ans) qmax(ls(id),x,y);if(vr>=ans) qmax(rs(id),x,y);} else{if(vr>=ans) qmax(rs(id),x,y);if(vl>=ans) qmax(ls(id),x,y);}
}