2021.07.09 K-D树
前置知识
1.二叉搜索树
2.总是很长的替罪羊树
K-D树
建树
K-D树具有二叉搜索树的形态，对于每一个分类标准，小于标准的节点在父节点左边，大于标准的节点在父节点右边。
例如：有三个坐标(2,2),(5,1),(6,4)，x轴以5为标准，则(2,2)为(5,1)左儿子，(6,4)为(5,1)右儿子。
常见的建树方法有两个：
1.交替
从根节点出发，依次把k个维度作主要关键词。
例如：第一层以x轴坐标为关键词，第二层以y轴坐标为关键词，第三层还是以x轴坐标为关键词。
代码如下：
void build(int &x,int l,int r,int type){//type是现在的标准是第几维度
if(l>r)return ;
x=++cnt;
cmptype=type;
int mid=(l+r)>>1;
nth_element(q+l,q+mid,q+r+1);
t[x]=q[mid];
build(t[x].ls,l,mid-1,type^1);//原题只有二维，用0，1表示即可
build(t[x].rs,mid+1,r,type^1);
update(x);
}
2.方差
但是对于数据分布极不均匀的情况，交替k个维度依次作为主要关键词就比较鸡肋。我们算出每个维度的方差，选取方差大的维度为主要关键词。
例如：对于一块豆腐，一横一竖平切一刀，再一横一竖平切一刀能起出来整齐的豆腐块（保不好是豆腐渣），但是对于厚度仅为几毫米的作业本，一横一竖平切一刀就令人十分暴躁，毕竟多次对于那可怜的几毫米切分，手一抖，寒假作业就得重写。
int build(int l,int r){
if(l>r)return 0;
int mid=(l+r)>>1;
double avx=0,avy=0,xi=0,yi=0;
for(int i=l;i<=r;i++){
avx+=s[i].x;
avy+=s[i].y;
}
avx/=(double)(r-l+1);//average 平均值
avy/=(double)(r-l+1);
for(int i=l;i<=r;i++){
xi+=(avx-s[i].x)*(avx-s[i].x);//variance 方差
yi+=(avy-s[i].y)*(avy-s[i].y);
}
if(xi>=yi)nth_element(s+l,s+mid,s+r+1,cmp1);
else nth_element(s+l,s+mid,s+r+1,cmp2);
ls[mid]=build(l,mid-1);rs[mid]=build(mid+1,r);
update(mid);
return mid;
}
用处
1.邻域查询
邻域查询有两种（实际一种）方法：
1.估计每一个节点能到达的最远最近距离，一般与方差建树连用（毕竟我没有与交替建树连用过）
例如：
[P2479 SDOI2010]捉迷藏 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
查询几个点之间最大最小曼哈顿距离的差
代码如下（此代码超时）：
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<cmath>
using namespace std;
const int N=1e5+10;
int n,ls[N],rs[N];
int L[N],R[N],D[N],U[N],maxn=-1,minn=1e9;
struct node{
int x,y;
}s[N];
inline int read(){
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')w=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
s=s*10+ch-'0';
ch=getchar();
}
return s*w;
}
bool cmp1(node a,node b){
return a.x<b.x;
}
bool cmp2(node a,node b){
return a.y<b.y;
}
void update(int x){
L[x]=R[x]=s[x].x;
D[x]=U[x]=s[x].y;
if(ls[x]){//每次更新x点能到的最值。L为x轴最小值，R为x轴最大值，D为y轴最小值，U为y轴最大值
L[x]=min(L[x],L[ls[x]]);R[x]=max(R[x],R[ls[x]]);
D[x]=min(D[x],D[ls[x]]);U[x]=max(U[x],U[ls[x]]);
}
if(rs[x]){
L[x]=min(L[x],L[rs[x]]);R[x]=max(R[x],R[rs[x]]);
D[x]=min(D[x],D[rs[x]]);U[x]=max(U[x],U[rs[x]]);
}
}
int build(int l,int r){
if(l>r)return 0;
int mid=(l+r)>>1;
double avx=0,avy=0,xi=0,yi=0;
for(int i=l;i<=r;i++){
avx+=s[i].x;
avy+=s[i].y;
}
avx/=(double)(r-l+1);
avy/=(double)(r-l+1);
for(int i=l;i<=r;i++){
xi+=(avx-s[i].x)*(avx-s[i].x);
yi+=(avy-s[i].y)*(avy-s[i].y);
}
if(xi>=yi)nth_element(s+l,s+mid,s+r+1,cmp1);
else nth_element(s+l,s+mid,s+r+1,cmp2);
ls[mid]=build(l,mid-1);rs[mid]=build(mid+1,r);
update(mid);
return mid;
}
int calc(int x,int aim){//估算x节点能到的最大距离
int ans=0;
//直接找上距离最远的点，上去硬怼，因为是这棵子树所有点中极值，只能起到估算的作用，而不是具体值，正确性嘛，自己思考一下如何？画个图就出来了哈。
ans+=max(abs(s[x].x-L[aim]),abs(s[x].x-R[aim]));
ans+=max(abs(s[x].y-D[aim]),abs(s[x].y-U[aim]));
return ans;
}
int calci(int x,int aim){//估算x节点能到的最小距离
int ans=0;
//最小的点是不是硬怼？那肯定啊，找上距离最小的点上去硬怼。只不过这是变形了一下。如果x在L和R的范围内，这个x轴都就不用管了，毕竟在这棵子树内，有可能是平行于y轴的线，对于y与D、U同理
if(s[x].x<L[aim])ans+=(L[aim]-s[x].x);
if(s[x].x>R[aim])ans+=(s[x].x-R[aim]);
if(s[x].y<D[aim])ans+=(s[x].y-D[aim]);
if(s[x].y>U[aim])ans+=(U[aim]-s[x].y);
return ans;
}
int dis(int a,int b){
return abs(s[a].x-s[b].x)+abs(s[a].y-s[b].y);
}
void querymin(int l,int r,int x){
if(l>r)return ;
int mid=(l+r)>>1;
if(x!=mid)minn=min(minn,dis(x,mid));
if(l==r)return ;
int disl=calci(x,ls[mid]),disr=calci(x,rs[mid]);
if(disl<minn&&disr<minn){
if(disl<disr){
querymin(l,mid-1,x);
if(disr<minn)querymin(mid+1,r,x);//以下类似的几处都是剪枝优化，要不然TLE到让你崩溃
//在query(l,mid-1,x)时已经更新了一次（也可能没更新）minn的值，如果disr仍小于minn，再继续更新，否则，扔它那儿嘛~
}else{
querymin(mid+1,r,x);
if(disl<minn)querymin(l,mid-1,x);
}
}else{
if(disl<minn)querymin(l,mid-1,x);
if(disr<minn)querymin(mid+1,r,x);
}
}
void querymax(int l,int r,int x){
if(l>r)return ;
int mid=(l+r)>>1;
if(x!=mid)maxn=max(maxn,dis(x,mid));
if(l==r)return ;
int disl=calc(x,ls[mid]),disr=calc(x,rs[mid]);
if(disl>maxn&&disr>maxn){
if(disl>disr){
querymax(l,mid-1,x);
if(disr>maxn)querymax(mid+1,r,x);
}else{
querymax(mid+1,r,x);
if(disl>maxn)querymax(l,mid-1,x);
}
}else{
if(disl>maxn)querymax(l,mid-1,x);
if(disr>maxn)querymax(mid+1,r,x);
}
}
int main(){
n=read();
for(int i=1;i<=n;i++){
s[i].x=read();s[i].y=read();
}
build(1,n);
int fin=1e9;
for(int i=1;i<=n;i++){
maxn=0;minn=1e9;
querymax(1,n,i);
querymin(1,n,i);
fin=min(fin,maxn-minn);
}
cout<<fin;
return 0;
}
2.实际上与上一种思路一样，只不过写起来不太一样，尤其是交替建树，刚学会，我害怕忘了，分开写一下
例如：
还是P2479（毕竟求最大值与最小值还弄一块儿的题不好找啊）
代码如下：
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
using namespace std;
const int N=1e5+10;
const int inf=1e9;
int cmptype;
struct kdtree{
struct node{
int num[2],minn[2],maxn[2];
int ls,rs;
bool operator <(const node &b)const{
return num[cmptype]<b.num[cmptype];
}
};
node a[N];
node t[N];
int rt,cnt;
kdtree(){rt=0;cnt=0;};
void update(int x){
t[x].minn[0]=t[x].maxn[0]=t[x].num[0];
t[x].minn[1]=t[x].maxn[1]=t[x].num[1];
if(t[x].ls){
t[x].minn[0]=min(t[x].minn[0],t[t[x].ls].minn[0]);
t[x].maxn[0]=max(t[x].maxn[0],t[t[x].ls].maxn[0]);
t[x].minn[1]=min(t[x].minn[1],t[t[x].ls].minn[1]);
t[x].maxn[1]=max(t[x].maxn[1],t[t[x].ls].maxn[1]);
}
if(t[x].rs){
t[x].minn[0]=min(t[x].minn[0],t[t[x].rs].minn[0]);
t[x].maxn[0]=max(t[x].maxn[0],t[t[x].rs].maxn[0]);
t[x].minn[1]=min(t[x].minn[1],t[t[x].rs].minn[1]);
t[x].maxn[1]=max(t[x].maxn[1],t[t[x].rs].maxn[1]);
}
}
void build(int &x,int l,int r,int type){
if(l>r){
x=0;
return ;
}
cmptype=type;
int mid=(l+r)>>1;
nth_element(a+l,a+mid,a+r+1);
t[x=++cnt]=a[mid];
build(t[x].ls,l,mid-1,type^1);
build(t[x].rs,mid+1,r,type^1);
update(x);
}
int dis(node u,node v){
return abs(u.num[0]-v.num[0])+abs(u.num[1]-v.num[1]);
}
node ti;
int ans;
int getmax(int x){//上去硬怼最大
if(!x)return -inf;
int fin=0;
fin+=max(abs(ti.num[0]-t[x].minn[0]),abs(ti.num[0]-t[x].maxn[0]));
fin+=max(abs(ti.num[1]-t[x].minn[1]),abs(ti.num[1]-t[x].maxn[1]));
return fin;
}
void querymax(int x){
if(!x)return ;
ans=max(ans,dis(ti,t[x]));
int disl=getmax(t[x].ls),disr=getmax(t[x].rs);
if(disl>disr){
if(disl>ans)querymax(t[x].ls);
if(disr>ans)querymax(t[x].rs);
}else{
if(disr>ans)querymax(t[x].rs);
if(disl>ans)querymax(t[x].ls);
}
}
int getmin(int x){//上去硬怼最小，至于为什么与零比较，很简单，无论是大于零还是小于零，都说明这条线不可能与x轴或y轴平行，想要距离最小，肯定选与水平或竖直的线，谁会选个斜边出来？
if(!x)return inf;
int fin=0;
fin+=max(t[x].minn[0]-ti.num[0],0);
fin+=max(ti.num[0]-t[x].maxn[0],0);
fin+=max(t[x].minn[1]-ti.num[1],0);
fin+=max(ti.num[1]-t[x].maxn[1],0);
return fin;
}
void querymin(int x){
if(!x)return ;
int tmp=dis(ti,t[x]);
if(tmp)ans=min(tmp,ans);
int disl=getmin(t[x].ls),disr=getmin(t[x].rs);
if(disl<disr){
if(disl<ans)querymin(t[x].ls);
if(disr<ans)querymin(t[x].rs);
}else{
if(disr<ans)querymin(t[x].rs);
if(disl<ans)querymin(t[x].ls);
}
}
int query(int x,int y,int type){
ti.num[0]=x;ti.num[1]=y;
if(!type)ans=inf,querymin(rt);
else ans=-inf,querymax(rt);
return ans;
}
}tree;
inline int read(){
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')w=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
s=s*10+ch-'0';
ch=getchar();
}
return s*w;
}
int main(){
int n;
n=read();
for(int i=1;i<=n;i++){
tree.a[i].num[0]=read();
tree.a[i].num[1]=read();
}
tree.build(tree.rt,1,n,0);
int fin=inf;
for(int i=1;i<=n;i++){
int x=tree.a[i].num[0],y=tree.a[i].num[1];
int u=tree.query(x,y,1),v=tree.query(x,y,0);
fin=min(fin,u-v);
}
cout<<fin;
return 0;
}
2.插入
无论是怎么建树，想要维持平衡（矮胖的身材）不至于退化，那就要想替罪羊树一样，用权值平衡，当某棵子树的大小大于总大小乘权值，那就重构，pia~权值越趋近于0.5，树就越平衡，越趋近于1，树就越倾向于链的形态。
1.方差建树+插入
例如：
[P4390 BOI2007]Mokia 摩基亚 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;
const int N=5e5+10;
const double alpha=0.75;
int n,rt,cnt,top,ls[N],rs[N],L[N],R[N],D[N],U[N],size[N],xh[N],sum[N],flag[N];
int x1,y1,x2,y2,lnum;
struct node{
int x,y,val;
}s[N];
inline int read(){
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')w=-1;
ch=getchar();
}
while(ch<='9'&&ch>='0'){
s=s*10+ch-'0';
ch=getchar();
}
return s*w;
}
bool cmp1(int a,int b){
return s[a].x<s[b].x;
}
bool cmp2(int a,int b){
return s[a].y<s[b].y;
}
void update(int x){
L[x]=R[x]=s[x].x;
U[x]=D[x]=s[x].y;
size[x]=size[ls[x]]+size[rs[x]]+1;
sum[x]=sum[ls[x]]+sum[rs[x]]+s[x].val;
if(ls[x]){
L[x]=min(L[x],L[ls[x]]);R[x]=max(R[x],R[ls[x]]);
D[x]=min(D[x],D[ls[x]]);U[x]=max(U[x],U[ls[x]]);
}
if(rs[x]){
L[x]=min(L[x],L[rs[x]]);R[x]=max(R[x],R[rs[x]]);
D[x]=min(D[x],D[rs[x]]);U[x]=max(U[x],U[rs[x]]);
}
}
int build(int l,int r){
if(l>r)return 0;
int mid=(l+r)>>1;
double avx=0,avy=0,xi=0,yi=0;
for(int i=l;i<=r;i++){
avx+=s[xh[i]].x;
avy+=s[xh[i]].y;
}
avx/=(double)(r-l+1);
avy/=(double)(r-l+1);
for(int i=l;i<=r;i++){
xi+=(avx-s[xh[i]].x)*(avx-s[xh[i]].x);
yi+=(avy-s[xh[i]].y)*(avy-s[xh[i]].y);
}
if(xi>yi){
flag[xh[mid]]=1;
nth_element(xh+l,xh+mid,xh+r+1,cmp1);//3.排排坐，吃果果。排序在此~
}else{
flag[xh[mid]]=2;
nth_element(xh+l,xh+mid,xh+r+1,cmp2);//3.这里也是排序
}
ls[xh[mid]]=build(l,mid-1);rs[xh[mid]]=build(mid+1,r);
update(xh[mid]);
return xh[mid];
}
void markedown(int x){//1.把要重构的子树记录下来
if(!x)return ;
markedown(ls[x]);
xh[++top]=x;
markedown(rs[x]);
}
void rebuild(int &x){
top=0;
markedown(x);
x=build(1,top);//2.重构。可是没有排序啊？
}
bool reflag(int x){//0.判断是否要重构
return (double)alpha*size[x]<=(double)max(size[ls[x]],size[rs[x]]);
}
void insert(int &x,int k){//-1.插入
if(!x){//节点不存在就自己造节点
x=k;
update(x);
return ;
}
if(flag[x]==1){//flag是记录建树标准的，依据建树标准插入节点。这里1代表以x轴为标准，2代表以y轴为标准
if(s[k].x<=s[x].x)insert(ls[x],k);
else insert(rs[x],k);
}else{//不过flag在这里还有可能等于零，那是还没有重构过的子树，都扔到这里自生自灭
if(s[k].y<s[x].y)insert(ls[x],k);
else insert(rs[x],k);
}
update(x);
if(reflag(x))rebuild(x);
}
int query(int x){
if(!x)return 0;
if(x2<L[x]||x1>R[x]||y1>U[x]||y2<D[x])return 0;
if(x1<=L[x]&&x2>=R[x]&&y1<=D[x]&&y2>=U[x])return sum[x];
int ans=0;
if(x1<=s[x].x&&x2>=s[x].x&&y1<=s[x].y&&y2>=s[x].y)ans+=s[x].val;
return query(ls[x])+query(rs[x])+ans;
}
int main(){
int op;
while(~scanf("%d",&op)&&op!=3){
if(op==0)n=read();
else if(op==1){
++cnt;
s[cnt].x=read();s[cnt].y=read();s[cnt].val=read();
insert(rt,cnt);
}else if(op==2){
x1=read();y1=read();x2=read();y2=read();
cout<<query(rt)<<endl;
}
}
return 0;
}
2.交替建树+插入
思路一样，写法不同
例如：
[P4169 [Violet]天使玩偶/SJY摆棋子 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)](https://www.luogu.com.cn/problem/P41
代码如下（代码来自他人）：
#include<cstdio>
#include<cstring>
#include<algorithm>
#define rate (0.75)
using namespace std;
const int mn = 1000005, inf = 0x3f3f3f3f;
int root, tmp, cnt, x, y, ans, pos[mn], top;
struct kd{
int p[2], mins[2], maxs[2], lch, rch, siz;
bool operator <(const kd a) const {return p[tmp] == a.p[tmp] ? p[tmp ^ 1] < a.p[tmp ^ 1] : p[tmp] < a.p[tmp];}
}t[mn], a[mn];
inline void init(int s) {t[s].maxs[0] = t[s].mins[0] = t[s].p[0], t[s].maxs[1] = t[s].mins[1] = t[s].p[1], t[s].siz = 1, t[s].lch = t[s].rch = 0;}
inline int ab(int x) {return x < 0 ? -x : x;}
inline int get_exp(int s){return max(x-t[s].maxs[0], 0) + max(t[s].mins[0]-x, 0) + max(t[s].mins[1]-y, 0) + max(y-t[s].maxs[1], 0);}
inline int get_pos(){return top ? pos[top--] : ++cnt;}
inline void getint(int &x)
{
x = 0; int flag = 1; char c;
while((c = getchar()) < '0' || c > '9') if(c == '-') flag = -1;
while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
x *= flag;
}
inline void update(int x, int y)
{
t[x].maxs[0] = max(t[x].maxs[0], t[y].maxs[0]), t[x].mins[0] = min(t[x].mins[0], t[y].mins[0]);
t[x].maxs[1] = max(t[x].maxs[1], t[y].maxs[1]), t[x].mins[1] = min(t[x].mins[1], t[y].mins[1]);
}
inline int make_tree(int l, int r, int d)
{
tmp = d; int mid = (l + r) >> 1, s = get_pos();
nth_element(a + l, a + mid, a + r + 1), t[s] = a[mid], init(s);
if(l < mid) t[s].lch = make_tree(l, mid - 1, d ^ 1), update(s, t[s].lch), t[s].siz += t[t[s].lch].siz;
if(mid < r) t[s].rch = make_tree(mid + 1, r, d ^ 1), update(s, t[s].rch), t[s].siz += t[t[s].rch].siz;
return s;
}
void pia(int s, int num)
{
if(t[s].lch) pia(t[s].lch, num);
a[num + t[t[s].lch].siz + 1] = t[s], pos[++top] = s;
if(t[s].rch) pia(t[s].rch, num + t[t[s].lch].siz + 1);
}
void ins(int &s, int to, int d)
{
update(s, to), ++t[s].siz;
if(t[to].p[d] <= t[s].p[d])
{
if(!t[s].lch) {t[s].lch = to; return;}
else ins(t[s].lch, to, d ^ 1);
}
else
{
if(!t[s].rch) {t[s].rch = to; return;}
else ins(t[s].rch, to, d ^ 1);
}
if(t[t[s].lch].siz > t[s].siz * rate || t[t[s].rch].siz > t[s].siz * rate)
pia(s, 0), s = make_tree(1, t[s].siz, d);
}
inline void get_ans(int s)
{
if(!s)
return;
ans = min(ans, ab(x - t[s].p[0]) + ab(y - t[s].p[1]));
int l_exp = t[s].lch ? get_exp(t[s].lch) : inf, r_exp = t[s].rch ? get_exp(t[s].rch) : inf;
if(l_exp < r_exp) {if(l_exp < ans) get_ans(t[s].lch); if(r_exp < ans) get_ans(t[s].rch);}
else {if(r_exp < ans) get_ans(t[s].rch); if(l_exp < ans) get_ans(t[s].lch);}
}
int main()
{
int n, m, i, T;
getint(n), getint(m);
for(i = 1; i <= n; i++)
getint(a[i].p[0]), getint(a[i].p[1]);
root = make_tree(1, n, 0);
while(m--)
{
getint(T);
if(T == 1)
++n, getint(t[n].p[0]), getint(t[n].p[1]), init(n), ins(root, n, 0);
else
ans = inf, getint(x), getint(y), get_ans(root), printf("%d\n", ans);
}
}
练习题
P4475 巧克力王国 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
代码如下：
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
#define int long long
const int N=5e4+10;
int n,m,cnt,cmptype,root;
int a,b,c;
struct node{
int num[2],maxn[2],minn[2];
int ls,rs,val,sum;
bool operator <(const node &b)const{
return num[cmptype]<b.num[cmptype];
}
}q[N],t[N];
inline int read(){
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')w=-1;
ch=getchar();
}
while(ch<='9'&&ch>='0'){
s=s*10+ch-'0';
ch=getchar();
}
return s*w;
}
void update(int x){
t[x].sum=t[t[x].ls].sum+t[t[x].rs].sum+t[x].val;
t[x].maxn[0]=t[x].minn[0]=t[x].num[0];
t[x].maxn[1]=t[x].minn[1]=t[x].num[1];
if(t[x].ls){
t[x].minn[0]=min(t[x].minn[0],t[t[x].ls].minn[0]);
t[x].maxn[0]=max(t[x].maxn[0],t[t[x].ls].maxn[0]);
t[x].minn[1]=min(t[x].minn[1],t[t[x].ls].minn[1]);
t[x].maxn[1]=max(t[x].maxn[1],t[t[x].ls].maxn[1]);
}
if(t[x].rs){
t[x].minn[0]=min(t[x].minn[0],t[t[x].rs].minn[0]);
t[x].maxn[0]=max(t[x].maxn[0],t[t[x].rs].maxn[0]);
t[x].minn[1]=min(t[x].minn[1],t[t[x].rs].minn[1]);
t[x].maxn[1]=max(t[x].maxn[1],t[t[x].rs].maxn[1]);
}
}
void build(int &x,int l,int r,int type){
if(l>r)return ;
x=++cnt;
cmptype=type;
int mid=(l+r)>>1;
nth_element(q+l,q+mid,q+r+1);
t[x]=q[mid];
build(t[x].ls,l,mid-1,type^1);
build(t[x].rs,mid+1,r,type^1);
update(x);
}
bool check(int x,int y){
return a*x+b*y<c;
}
int query(int x){
int tot=0;
tot+=check(t[x].minn[0],t[x].minn[1]);
tot+=check(t[x].minn[0],t[x].maxn[1]);
tot+=check(t[x].maxn[0],t[x].maxn[1]);
tot+=check(t[x].maxn[0],t[x].minn[1]);
if(tot==4)return t[x].sum;
if(!tot)return 0;
int res=0;
if(check(t[x].num[0],t[x].num[1]))res+=t[x].val;
if(t[x].ls)res+=query(t[x].ls);
if(t[x].rs)res+=query(t[x].rs);
return res;
}
signed main(){
n=read();m=read();
for(int i=1;i<=n;i++){
q[i].num[0]=read();q[i].num[1]=read();q[i].val=read();
}
build(root,1,n,0);
for(int i=1;i<=m;i++){
a=read();b=read();c=read();
cout<<query(root)<<endl;
}
return 0;
}
[P2093 国家集训队]JZPFAR - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
#define int long long
const int inf=0x7fffffff;
const int N=1e5+10;
int n,m,cmptype,cnt,root,X,Y;
struct node{
int dis,id;
/*bool operator <(const node &b)const{
return dis==b.dis?id>b.id:dis>b.dis;//
}*/
};
bool operator <(node a,node b){
return a.dis>b.dis||(a.dis==b.dis&&a.id<b.id);
}
priority_queue<node>q;
struct nodei{
int x[2],id;
bool operator <(const nodei &b)const{
return x[cmptype]<b.x[cmptype];
}
}p[N];
struct tree{
nodei p;
int maxn[2],minn[2],ls,rs,id;
}t[N];
inline int read(){
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')w=-1;
ch=getchar();
}
while(ch<='9'&&ch>='0'){
s=s*10+ch-'0';
ch=getchar();
}
return s*w;
}
int dis(tree x){
int ans=0;
ans=(x.p.x[0]-X)*(x.p.x[0]-X)+(x.p.x[1]-Y)*(x.p.x[1]-Y);
return ans;
}
int calc(tree x){
int ans=0;
ans+=max((x.minn[0]-X)*(x.minn[0]-X),(x.maxn[0]-X)*(x.maxn[0]-X));
ans+=max((x.minn[1]-Y)*(x.minn[1]-Y),(x.maxn[1]-Y)*(x.maxn[1]-Y));
return ans;
}
void update(int x){
t[x].maxn[0]=t[x].minn[0]=t[x].p.x[0];
t[x].maxn[1]=t[x].minn[1]=t[x].p.x[1];
//if(!x)return ;
if(t[x].ls){
t[x].minn[0]=min(t[x].minn[0],t[t[x].ls].minn[0]);
t[x].maxn[0]=max(t[x].maxn[0],t[t[x].ls].maxn[0]);
t[x].minn[1]=min(t[x].minn[1],t[t[x].ls].minn[1]);
t[x].maxn[1]=max(t[x].maxn[1],t[t[x].ls].maxn[1]);
}
if(t[x].rs){
t[x].minn[0]=min(t[x].minn[0],t[t[x].rs].minn[0]);
t[x].maxn[0]=max(t[x].maxn[0],t[t[x].rs].maxn[0]);
t[x].minn[1]=min(t[x].minn[1],t[t[x].rs].minn[1]);
t[x].maxn[1]=max(t[x].maxn[1],t[t[x].rs].maxn[1]);
}
}
void build(int &x,int l,int r,int type){
if(l>r)return ;
x=++cnt;
cmptype=type;
int mid=(l+r)>>1;
nth_element(p+l,p+mid,p+r+1);
t[x].p=p[mid];t[x].id=t[x].p.id;
build(t[x].ls,l,mid-1,type^1);
build(t[x].rs,mid+1,r,type^1);
update(x);
}
void query(int x){
if(!x)return ;
int res=dis(t[x]);
if(res>q.top().dis||(res==q.top().dis&&t[x].id<q.top().id)){
q.pop();
q.push((node){res,t[x].id});
}
int disl=inf,disr=inf;
if(t[x].ls)disl=calc(t[t[x].ls]);
if(t[x].rs)disr=calc(t[t[x].rs]);
if(disl>disr){
if(disl>=q.top().dis)query(t[x].ls);
if(disr>=q.top().dis)query(t[x].rs);
}else{
if(disr>=q.top().dis)query(t[x].rs);
if(disl>=q.top().dis)query(t[x].ls);
}
}
signed main(){
n=read();
for(int i=1;i<=n;i++){
p[i].x[0]=read();p[i].x[1]=read();p[i].id=i;
}
build(root,1,n,0);
m=read();
for(int i=1;i<=m;i++){
while(!q.empty())q.pop();
X=read();Y=read();
int k=read();
for(int j=1;j<=k;j++)q.push((node){-1,0});
query(root);
cout<<q.top().id<<endl;
}
return 0;
}
P4148 简单题 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;
const int N=5e5+10;
const double alpha=0.75;
int n,rt,cnt,top,ls[N],rs[N],L[N],R[N],D[N],U[N],size[N],xh[N],sum[N],flag[N];
int x1,y1,x2,y2,lnum;
struct node{
int x,y,val;
}s[N];
inline int read(){
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')w=-1;
ch=getchar();
}
while(ch<='9'&&ch>='0'){
s=s*10+ch-'0';
ch=getchar();
}
return s*w;
}
bool cmp1(int a,int b){
return s[a].x<s[b].x;
}
bool cmp2(int a,int b){
return s[a].y<s[b].y;
}
void update(int x){
L[x]=R[x]=s[x].x;
U[x]=D[x]=s[x].y;
size[x]=size[ls[x]]+size[rs[x]]+1;
sum[x]=sum[ls[x]]+sum[rs[x]]+s[x].val;
if(ls[x]){
L[x]=min(L[x],L[ls[x]]);R[x]=max(R[x],R[ls[x]]);
D[x]=min(D[x],D[ls[x]]);U[x]=max(U[x],U[ls[x]]);
}
if(rs[x]){
L[x]=min(L[x],L[rs[x]]);R[x]=max(R[x],R[rs[x]]);
D[x]=min(D[x],D[rs[x]]);U[x]=max(U[x],U[rs[x]]);
}
}
int build(int l,int r){
if(l>r)return 0;
int mid=(l+r)>>1;
double avx=0,avy=0,xi=0,yi=0;
for(int i=l;i<=r;i++){
avx+=s[xh[i]].x;
avy+=s[xh[i]].y;
}
avx/=(double)(r-l+1);
avy/=(double)(r-l+1);
for(int i=l;i<=r;i++){
xi+=(avx-s[xh[i]].x)*(avx-s[xh[i]].x);
yi+=(avy-s[xh[i]].y)*(avy-s[xh[i]].y);
}
if(xi>yi){
flag[xh[mid]]=1;
nth_element(xh+l,xh+mid,xh+r+1,cmp1);
}else{
flag[xh[mid]]=2;
nth_element(xh+l,xh+mid,xh+r+1,cmp2);
}
ls[xh[mid]]=build(l,mid-1);rs[xh[mid]]=build(mid+1,r);
update(xh[mid]);
return xh[mid];
}
void markedown(int x){
if(!x)return ;
markedown(ls[x]);
xh[++top]=x;
markedown(rs[x]);
}
void rebuild(int &x){
top=0;
markedown(x);
x=build(1,top);
}
bool reflag(int x){
return (double)alpha*size[x]<=(double)max(size[ls[x]],size[rs[x]]);
}
void insert(int &x,int k){
if(!x){
x=k;
update(x);
return ;
}
if(flag[x]==1){
if(s[k].x<=s[x].x)insert(ls[x],k);
else insert(rs[x],k);
}else{
if(s[k].y<s[x].y)insert(ls[x],k);
else insert(rs[x],k);
}
update(x);
if(reflag(x))rebuild(x);
}
int query(int x){
if(!x)return 0;
if(x2<L[x]||x1>R[x]||y1>U[x]||y2<D[x])return 0;
if(x1<=L[x]&&x2>=R[x]&&y1<=D[x]&&y2>=U[x])return sum[x];
int ans=0;
if(x1<=s[x].x&&x2>=s[x].x&&y1<=s[x].y&&y2>=s[x].y)ans+=s[x].val;
return query(ls[x])+query(rs[x])+ans;
}
int main(){
n=read();
int op;
while(~scanf("%d",&op)&&op!=3){
if(op==1){
++cnt;
s[cnt].x=read()^lnum;s[cnt].y=read()^lnum;s[cnt].val=read()^lnum;
insert(rt,cnt);
}else if(op==2){
x1=read();y1=read();x2=read();y2=read();
x1^=lnum;x2^=lnum;y1^=lnum;y2^=lnum;
lnum=query(rt);
cout<<lnum<<endl;
}
}
return 0;
}
[P6247 SDOI2012]最近最远点对 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
using namespace std;
const int N=1e5+10;
int n,ls[N],rs[N];
double L[N],R[N],D[N],U[N],maxn=-0.1,minn=2e18;
struct node{
double x,y;
}s[N];
inline int read(){
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')w=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
s=s*10+ch-'0';
ch=getchar();
}
return s*w;
}
bool cmp1(node a,node b){
return a.x<b.x;
}
bool cmp2(node a,node b){
return a.y<b.y;
}
void update(int x){
L[x]=R[x]=s[x].x;
D[x]=U[x]=s[x].y;
if(ls[x]){
L[x]=min(L[x],L[ls[x]]);R[x]=max(R[x],R[ls[x]]);
D[x]=min(D[x],D[ls[x]]);U[x]=max(U[x],U[ls[x]]);
}
if(rs[x]){
L[x]=min(L[x],L[rs[x]]);R[x]=max(R[x],R[rs[x]]);
D[x]=min(D[x],D[rs[x]]);U[x]=max(U[x],U[rs[x]]);
}
}
int build(int l,int r){
if(l>r)return 0;
int mid=(l+r)>>1;
double avx=0,avy=0,xi=0,yi=0;
for(int i=l;i<=r;i++){
avx+=s[i].x;
avy+=s[i].y;
}
avx/=(double)(r-l+1);
avy/=(double)(r-l+1);
for(int i=l;i<=r;i++){
xi+=(avx-s[i].x)*(avx-s[i].x);
yi+=(avy-s[i].y)*(avy-s[i].y);
}
if(xi>=yi)nth_element(s+l,s+mid,s+r+1,cmp1);
else nth_element(s+l,s+mid,s+r+1,cmp2);
ls[mid]=build(l,mid-1);rs[mid]=build(mid+1,r);
update(mid);
return mid;
}
double calc(int x,int aim){
double ans=0;
/*if(s[x].x<L[aim])ans+=(s[x].x-L[aim])*(s[x].x-L[aim]);
if(s[x].x>R[aim])ans+=(s[x].x-R[aim])*(s[x].x-R[aim]);
if(s[x].y<D[aim])ans+=(s[x].y-D[aim])*(s[x].y-D[aim]);
if(s[x].y>U[aim])ans+=(s[x].y-U[aim])*(s[x].y-U[aim]);*/
ans+=max((s[x].x-L[aim])*(s[x].x-L[aim]),(s[x].x-R[aim])*(s[x].x-R[aim]));
ans+=max((s[x].y-U[aim])*(s[x].y-U[aim]),(s[x].y-D[aim])*(s[x].y-D[aim]));
return ans;
}
double calci(int x,int aim){
double ans=0;
if(s[x].x<L[aim])ans+=(s[x].x-L[aim])*(s[x].x-L[aim]);
if(s[x].x>R[aim])ans+=(s[x].x-R[aim])*(s[x].x-R[aim]);
if(s[x].y<D[aim])ans+=(s[x].y-D[aim])*(s[x].y-D[aim]);
if(s[x].y>U[aim])ans+=(s[x].y-U[aim])*(s[x].y-U[aim]);
//ans+=min((s[x].x-L[aim])*(s[x].x-L[aim]),(s[x].x-R[aim])*(s[x].x-R[aim]));
//ans+=min((s[x].y-U[aim])*(s[x].y-U[aim]),(s[x].y-D[aim])*(s[x].y-D[aim]));
return ans;
}
double dis(int a,int b){
return (double)(s[a].x-s[b].x)*(s[a].x-s[b].x)+(double)(s[a].y-s[b].y)*(s[a].y-s[b].y);
}
void querymin(int l,int r,int x){
if(l>r)return ;
int mid=(l+r)>>1;
if(x!=mid)minn=min(minn,dis(x,mid));
if(l==r)return ;
double disl=calci(x,ls[mid]),disr=calci(x,rs[mid]);
if(disl<minn&&disr<minn){
if(disl<disr){
querymin(l,mid-1,x);
if(disr<minn)querymin(mid+1,r,x);
}else{
querymin(mid+1,r,x);
if(disl<minn)querymin(l,mid-1,x);
}
}else{
if(disl<minn)querymin(l,mid-1,x);
if(disr<minn)querymin(mid+1,r,x);
}
}
void querymax(int l,int r,int x){
if(l>r)return ;
int mid=(l+r)>>1;
if(x!=mid)maxn=max(maxn,dis(x,mid));
if(l==r)return ;
double disl=calc(x,ls[mid]),disr=calc(x,rs[mid]);
if(disl>maxn&&disr>maxn){
if(disl>disr){
querymax(l,mid-1,x);
if(disr>maxn)querymax(mid+1,r,x);
}else{
querymax(mid+1,r,x);
if(disl>maxn)querymax(l,mid-1,x);
}
}else{
if(disl>maxn)querymax(l,mid-1,x);
if(disr>maxn)querymax(mid+1,r,x);
}
}
int main(){
n=read();
for(int i=1;i<=n;i++){
cin>>s[i].x>>s[i].y;
//cout<<s[i].x<<" "<<s[i].y<<endl;//
}
//cout<<endl;//
build(1,n);
for(int i=1;i<=n;i++){
querymax(1,n,i);
querymin(1,n,i);
//cout<<maxn<<" "<<minn<<endl;//
}
printf("%.2lf %.2lf",(double)sqrt(minn),(double)sqrt(maxn));
return 0;
}
P1429 平面最近点对（加强版） - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
const int N=2e5+10;
int n,flag[N],ls[N],rs[N];
double L[N],R[N],D[N],U[N],ans=2e18;
struct node{
double x,y;
}s[N];
double dis(int a,int b){
return (s[a].x-s[b].x)*(s[a].x-s[b].x)+(s[a].y-s[b].y)*(s[a].y-s[b].y);
}
bool cmp1(node a,node b){
return a.x<b.x;
}
bool cmp2(node a,node b){
return a.y<b.y;
}
void update(int x){
L[x]=R[x]=s[x].x;
D[x]=U[x]=s[x].y;
if(ls[x]){
L[x]=min(L[x],L[ls[x]]);R[x]=max(R[x],R[ls[x]]);
D[x]=min(D[x],D[ls[x]]);U[x]=max(U[x],U[ls[x]]);
}
if(rs[x]){
L[x]=min(L[x],L[rs[x]]);R[x]=max(R[x],R[rs[x]]);
D[x]=min(D[x],D[rs[x]]);U[x]=max(U[x],U[rs[x]]);
}
}
int build(int l,int r){
if(l>r)return 0;
int mid=(l+r)>>1;
double avx=0,avy=0,xi=0,yi=0;
for(int i=l;i<=r;i++)avx+=s[i].x,avy+=s[i].y;
avx/=(double)(r-l+1);avy/=(double)(r-l+1);
for(int i=l;i<=r;i++){
xi+=(avx-s[i].x)*(avx-s[i].x);
yi+=(avy-s[i].y)*(avy-s[i].y);
}
if(xi>=yi){
//flag[mid]=1;
nth_element(s+l,s+mid,s+r+1,cmp1);
}else{
//flag[mid]=2;
nth_element(s+l,s+mid,s+r+1,cmp2);
}
ls[mid]=build(l,mid-1);rs[mid]=build(mid+1,r);
update(mid);
return mid;
}
double calc(int x,int aim){
double ansi=0;
if(L[aim]>s[x].x)ansi+=(L[aim]-s[x].x)*(L[aim]-s[x].x);
if(R[aim]<s[x].x)ansi+=(R[aim]-s[x].x)*(R[aim]-s[x].x);
if(D[aim]>s[x].y)ansi+=(D[aim]-s[x].y)*(D[aim]-s[x].y);
if(U[aim]<s[x].y)ansi+=(U[aim]-s[x].y)*(U[aim]-s[x].y);
return ansi;
}
void query(int l,int r,int x){
if(l>r)return ;
int mid=(l+r)>>1;
if(mid!=x)ans=min(ans,dis(x,mid));
if(l==r)return ;
double disl=calc(x,ls[mid]),disr=calc(x,rs[mid]);
if(disl<ans&&disr<ans){
if(disl<disr){
query(l,mid-1,x);
if(disr<ans)query(mid+1,r,x);
}else{
query(mid+1,r,x);
if(disl<ans)query(l,mid-1,x);
}
}else{
if(disl<ans)query(l,mid-1,x);
if(disr<ans)query(mid+1,r,x);
}
}
inline int read(){
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')w=-1;
ch=getchar();
}
while(ch<='9'&&ch>='0'){
s=s*10+ch-'0';
ch=getchar();
}
return s*w;
}
int main(){
n=read();
for(int i=1;i<=n;i++)cin>>s[i].x>>s[i].y;
build(1,n);
for(int i=1;i<=n;i++)query(1,n,i);
printf("%.4lf",sqrt(ans));
return 0;
}
[P4357 CQOI2016]K 远点对 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<queue>
using namespace std;
#define int long long
const int N=1e5+10;
int n,k,ls[N],rs[N],L[N],R[N],D[N],U[N];
struct node{
int x,y;
}s[N];
priority_queue<int,vector<int>,greater<int> >q;
inline int read(){
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')w==-1;
ch=getchar();
}
while(ch<='9'&&ch>='0'){
s=s*10+ch-'0';
ch=getchar();
}
return s*w;
}
bool cmp1(node x,node y){
return x.x<y.x;
}
bool cmp2(node x,node y){
return x.y<y.y;
}
void update(int x){
L[x]=R[x]=s[x].x;
D[x]=U[x]=s[x].y;
if(ls[x]){
L[x]=min(L[x],L[ls[x]]);R[x]=max(R[x],R[ls[x]]);
D[x]=min(D[x],D[ls[x]]);U[x]=max(U[x],U[ls[x]]);
}
if(rs[x]){
L[x]=min(L[x],L[rs[x]]);R[x]=max(R[x],R[rs[x]]);
D[x]=min(D[x],D[rs[x]]);U[x]=max(U[x],U[rs[x]]);
}
}
int build(int l,int r){
if(l>r)return 0;
int mid=(l+r)>>1;
double avx=0,avy=0,xi=0,yi=0;
for(int i=l;i<=r;i++){
avx+=s[i].x;avy+=s[i].y;
}
avx/=(double)(r-l+1);avy/=(double)(r-l+1);
for(int i=l;i<=r;i++){
xi+=(avx-s[i].x)*(avx-s[i].x);
yi+=(avy-s[i].y)*(avy-s[i].y);
}
if(xi>yi)nth_element(s+l,s+mid,s+r+1,cmp1);
else nth_element(s+l,s+mid,s+r+1,cmp2);
ls[mid]=build(l,mid-1);
rs[mid]=build(mid+1,r);
update(mid);
return mid;
}
int pf(int x){
return x*x;
}
int calc(int x,int aim){
return max(pf(s[x].x-L[aim]),pf(s[x].x-R[aim]))+
max(pf(s[x].y-D[aim]),pf(s[x].y-U[aim]));
}
void query(int l,int r,int x){
if(l>r)return ;
int mid=(l+r)>>1;
int now=pf(s[x].x-s[mid].x)+pf(s[x].y-s[mid].y);
if(now>q.top()){
q.pop();
q.push(now);
}
int disl=calc(x,ls[mid]),disr=calc(x,rs[mid]);
if(disl>q.top()&&disr>q.top()){
if(disl>disr){
query(l,mid-1,x);
if(disr>q.top())query(mid+1,r,x);
}else{
query(mid+1,r,x);
if(disl>q.top())query(l,mid-1,x);
}
}else{
if(disl>q.top())query(l,mid-1,x);
if(disr>q.top())query(mid+1,r,x);
}
}
signed main(){
n=read();k=read();
k*=2;
for(int i=1;i<=k;i++)q.push(0);
for(int i=1;i<=n;i++){
s[i].x=read();s[i].y=read();
}
build(1,n);
for(int i=1;i<=n;i++)query(1,n,i);
cout<<q.top();
return 0;
}
