luogu P3810(kd-tree)_新笑雨的博客-程序员秘密

技术标签: luogu  kd-tree  

题目链接

题意:三维偏序

kd-tree解法

首先暴力的kd-tree是3维的,过不去.所以需要先把一维排序,然后对剩下的2维建kd-tree

这个kd-tree是在线插入的,所以需要定时重构,然后重构的次数比较玄学,由于kd-tree本身复杂度 O ( n n ) O(n\sqrt n) O(nn )左右,所以块长一开始设成了 n \sqrt n n ,但是过不去(甚至没有3维的kd-tree暴力快),后来把块长*25,就卡过了.

注意插入的时候需要把排序的那一维全部相等的元素一起插入进去(或者插入完了以后一起查询),如果一个一个插入,会漏解,可能后插入的点可以被先插入的点覆盖.

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+5;
inline int read(){
    
	char c=getchar();int t=0,f=1;
	while(!isdigit(c)){
    if(c=='-')f=-1;c=getchar();}
	while(isdigit(c)){
    t=(t<<3)+(t<<1)+(c^48);c=getchar();}
	return t*f;
}
int n,k;
struct node{
    
	int a[3];
}a[maxn],b[maxn];
int opt;
bool cmp(node a,node b){
    
	return a.a[opt]<b.a[opt];
}
int ans,tim;
#define lc ch[x][0]
#define rc ch[x][1]
struct tree{
    
	int ch[maxn][2],mx[maxn][2],mn[maxn][2],cnt,rt,sz[maxn],dep[maxn];
	node p[maxn];
	inline void pushup(int x){
    
		sz[x]=1;
		for(int i=0;i<2;i++)mn[x][i]=mx[x][i]=p[x].a[i];
		if(lc){
    
			for(int i=0;i<2;i++){
    mn[x][i]=min(mn[x][i],mn[lc][i]);mx[x][i]=max(mx[x][i],mx[lc][i]);}
			sz[x]+=sz[lc];
		}
		if(rc){
    
			for(int i=0;i<2;i++){
    mn[x][i]=min(mn[x][i],mn[rc][i]);mx[x][i]=max(mx[x][i],mx[rc][i]);}
			sz[x]+=sz[rc];
		}
	}
	void insert(int &x,node q,int fa){
    
		//printf("%d %d %d\n",x,fa,cnt);
		if(!x){
    cnt++;x=cnt;dep[x]=dep[fa]+1;p[x]=q;pushup(x);return ;}
		opt=dep[x]&1;
		if(p[x].a[opt]<q.a[opt]){
    insert(rc,q,x);}
		else insert(lc,q,x);
		pushup(x);
	}
	void reset(int &x){
    
		if(lc)reset(lc);
		if(rc)reset(rc);
		for(int i=0;i<2;i++){
    mn[x][i]=mx[x][i]=p[x].a[i]=0;}
		sz[x]=0;dep[x]=0;ch[x][0]=ch[x][1]=0;x=0;
	}
	void rs(){
    cnt=0;}
	void build(int &x,int l,int r,int fa){
    if(l>r)return ;
		if(!x){
    
			cnt++;
			x=cnt;dep[x]=dep[fa]+1;//printf("%d %d %d %d\n",x,l,r,fa);
		}
		opt=dep[x]&1;int mid=(l+r)>>1;
	//	printf("%d\n",mid);
		nth_element(a+l,a+mid,a+r+1,cmp);p[x]=a[mid];
		build(lc,l,mid-1,x);build(rc,mid+1,r,x);
		pushup(x);
	}
	void query(int x,node q){
    
		if(!x)return ;
		int flag=1;
		for(int i=0;i<2;i++){
    if(p[x].a[i]>q.a[i]){
    flag=0;break;}}
		if(flag)ans++;
		flag=1;
		for(int i=0;i<2;i++){
    if(mx[lc][i]>q.a[i]){
    flag=0;break;}}
		if(flag)ans+=sz[lc];
		else{
    
			flag=1;
			for(int i=0;i<2;i++){
    if(mn[lc][i]>q.a[i]){
    flag=0;break;}}
			if(flag)query(lc,q);
		}
		flag=1;
		for(int i=0;i<2;i++){
    if(mx[rc][i]>q.a[i]){
    flag=0;break;}}
		if(flag)ans+=sz[rc];
		else{
    
			flag=1;
			for(int i=0;i<2;i++){
    if(mn[rc][i]>q.a[i]){
    flag=0;break;}}
			if(flag)query(rc,q);
		}
	}
}t;
int ton[maxn];
bool cmp1(node a,node b){
    
	return a.a[2]<b.a[2];
}
int main(){
    
	//freopen("3810.in","r",stdin);
	//freopen("3810.out","w",stdout);
	n=read(),k=read();
	for(int i=1;i<=n;i++){
    
		a[i].a[0]=read(),a[i].a[1]=read(),a[i].a[2]=read();
	}
	tim=25*sqrt(n);
	sort(a+1,a+1+n,cmp1);
	for(int i=1;i<=n;i++)b[i]=a[i];
	int lst=1;
	for(int i=1;i<=n;i++){
    
		//printf("%d %d %d %d\n",a[i].a[0],a[i].a[1],a[i].a[2],i);
		t.insert(t.rt,a[i],0);
		if(i%tim==0){
    
			t.reset(t.rt);t.rs();
			t.build(t.rt,1,i,0);
		}
		if(b[i].a[2]!=b[i+1].a[2]){
    
			for(int j=lst;j<=i;j++){
    
				ans=0;t.query(t.rt,b[j]);ans--;
			//	printf("%d %d %d %d\n",b[j].a[0],b[j].a[1],b[j].a[2],j);
				ton[ans]++;
			}
			lst=i+1;
		}
	}
	for(int i=0;i<n;i++){
    
		printf("%d\n",ton[i]);
	}
	return 0;
}

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/wmhtxdy/article/details/103762336

智能推荐

数据导入到EXCEL(EXCELHelper)_有问又问的博客-程序员秘密

using System;using System.Data;using System.IO;using System.Windows.Forms;using Microsoft.Office.Interop.Excel;namespace zzz.BusinessSystem{    public static class ExcelHelp    {

找xpath好用的工具(Firefox插件)_韩大帅666的博客-程序员秘密_火狐xpath插件

WebDriver Element Locator安装打开firefox浏览器,进入网址https://addons.mozilla.org/en-US/firefox/在搜索框里输入WebDriver Element Locator 点击Add to firefox 会有个弹出框,点击install now可以看从firefox浏览器的menu -> Tools -> A

聊聊前端面试_若川视野的博客-程序员秘密

大家好,我是若川。今天分享一篇面试相关的文章。点击下方卡片关注我、加个星标,或者查看源码等系列文章。学习源码整体架构系列、年度总结、JS基础系列最近 Zoom 国内又开放招聘了,我们...

java mysql 时间比较_数据库的九个日期函数&&时间比较_胡厨厨的博客-程序员秘密

1、NOW获取当前日期和时间的函数。语法: NOW()例如:select NOW();2、CURDATE获取当前的日期语法:CURDATE()3、CURTIME()获取当前时间语法:CURTIME()4、DATE获取日期时间或者日期的日期部分语法:DATE(date)date 参数是合法的日期表达式。例如:5、EXTRACT获取返回日期/时间的单独部分,比如年、月、日、小时、分钟等等。语法:EXT...

软件测试基础知识_小白菜666的博客-程序员秘密

软件测试基础知识一、软件测试发展历程  20世纪60年代(软件工程建立前),为表明程序正确而进行测试。1972年在北卡罗来纳大学举行了首届软件测试正式会议。1975 John Good Enough和Susan Gerhart在IEEE上发表了《测试数据选择的原理》的文章,软件测试被确定为一种研究方向。20世纪80年代早期,“质量”的号角开始吹响。软件测试定义发生了改变,测试不单纯是一一个发现错误...

python绘制圆角正方形,Python Imaging Library(PIL)图-带有渐变的圆角矩形_知之狐的博客-程序员秘密

I am trying to use PIL to draw a rectangle with rounded corners and a gradient fill for the color. I found a cool web site ( http://web.archive.org/web/20130306020911/http://nadiana.com/pil-tutorial-b...

随便推点

接口--php对接农行网上支付平台-b2b_anyun3065的博客-程序员秘密

对接农行网上支付平台从银行那边获取到对应的接口包将文件保存在网站的路径中我是destoon网站系统对接,就放在了api/pay/新建一个文件夹abc/下完成之后填写接口的配置文件路径:ebusclient/TrustMerchant.ini标出的内容 都是需要填写的 对应的证书,联系银行要配置完成之后 访问测试文件确定是否安装正确...

[转]腾讯开放云战略也杀来了!BAT各自搞什么云?_weixin_30815469的博客-程序员秘密

云计算已让“计算资源”像水和电一样统一调度和按需使用,开发者怎么选?罗超2013-09-09 06:55腾讯今天下午将召开“云开放战略发布会”,宣布正式对外开放。阿里和百度已进入开发者云市场多时,腾讯终于瞄准时机进入这个市场,BAT三家算是在云中在此短兵相接。过去开发网站要么完全靠自己从零开始;要么利用适合的第三方工具包,利用其提供的API进行上层开发;或者基于某套模板如...

音乐资源站_yourszhu的博客-程序员秘密

 深秋_燕子 http://zhangmen.baidu.com/promotion/10013/204409.html?pz=2 清水浮香  带歌词的哦!http://hi.baidu.com/%C7%E5%CB%AE%B8%A1%CF%E3/profile 

python画图设置字体大小_用python matplotlib进行画图的时候如何将中文字体设定成电脑上的指定字体和指定字号大小?..._weixin_39859909的博客-程序员秘密

import matplotlib as mplimport matplotlib.pyplot as pltzhfont1 = mpl.font_manager.FontProperties(fname=r'C:\Windows\Fonts\STKAITI.TTF',size=50)zhfont2 = mpl.font_manager.FontProperties(fname=r'C:\Wind...

测量学—误差理论与测量平差基础_挥剑段天涯的博客-程序员秘密

绪论观测误差测量平差学科的研究对象测量平差的简史和发展本课程的任务和内容误差分布与精度指标正态分布偶然误差的规律性衡量精度的指标精度、 准确度与精确度测量不确定度协方差传播律及权数学期望的传播协方差传播律协方差传播律的应用权与定权的常用方法协因数和协因数传播律由真误差计算中误差及其实际应用系统误差的传播平差数学模型与最小二乘原理测量平差概述函数模型函数模型的线性化测量平差的数学模型参数估计与最小二乘

推荐文章

热门文章

相关标签