HDU 5126 stars 4维偏序, CDQ套CDQ_dengpangbu3703的博客-程序员宅基地

技术标签: 数据结构与算法  

题目传送门

题意:在一个星空中,按着时间会出现一些点,现在john想知道,在某个时间内有多少个星星是的坐标是满足条件的。(x1<=x<=x2, y1 <= y <= y2, z1 <= z <= z2).
题解:先简化问题,如果我们就统计出现所有 x <= x2 , y <= y2, z <= z2的点的话,这就是一个4维偏序题。

对于这个统计点数来说, 我们先按照题目给定点的顺序来进行CDQ, 这样在CDQ内只有左边的添加点会对右边的询问点产生影响,然后我们再把这些会对答案找出影响的点拿出来,

对这些点进行关于X轴内一个sort,对于sort完的结果,我们再进行cdq, 这样在cdq内还是只有左边的左边的添加点会对右边的询问点产生影响,然后我们再把这些会对答案找出影响的点拿出来。

这样就变成了2维偏序题了, 再对y sort, 然后for一遍询问答案把答案加进去就好了。

 

现在的问题就变成了怎么询问这个长方体内点的个数。 我们可以用差分的思想去维护这个矩形。

我们对一次询问可以拆成8次询问。

Q1( X1-1, Y1-1, Z2) Q2 (X1-1, Y2, Z2) Q3 (X2, Y1-1, Z2) Q4(X2,Y2,Z2)

Q5( X1-1, Y1-1, Z1-1) Q6 (X1-1, Y2, Z1-1) Q7 (X2, Y1-1, Z1-1) Q8(X2,Y2,Z1-1)

可以发现 Q1-Q2-Q3+Q4 得到的是  z <= z2    x1<=x <= x2 && y1 <= y <= y2 的点的个数和。

现在我们在减去 z <= z1-1 x1<=x <= x2 && y1 <= y <= y2 的个数和就是答案了。

 

在CDQ的过程中, 我们可以加上一个剪枝 即对于这个CDQ来说,如果左边没有添加点 或者 右边没有询问点 就再进行处理了, 因为不会对答案造成影响。

代码:

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 #define Fopen freopen("_in.txt","r",stdin); freopen("_out.txt","w",stdout);
  4 #define LL long long
  5 #define ULL unsigned LL
  6 #define fi first
  7 #define se second
  8 #define pb push_back
  9 #define lson l,m,rt<<1
 10 #define rson m+1,r,rt<<1|1
 11 #define lch(x) tr[x].son[0]
 12 #define rch(x) tr[x].son[1]
 13 #define max3(a,b,c) max(a,max(b,c))
 14 #define min3(a,b,c) min(a,min(b,c))
 15 typedef pair<int,int> pll;
 16 const int inf = 0x3f3f3f3f;
 17 const LL INF = 0x3f3f3f3f3f3f3f3f;
 18 const LL mod =  (int)1e9+7;
 19 const int N = 1e6 + 100;
 20 struct Node{
 21     int x, y, z, op, id;
 22 }A[N], B[N], C[N];
 23 int ans[N];
 24 int zz[N];
 25 int tot = 0;
 26 int zsz;
 27 int bit[N];
 28 void add(int x, int v){
 29     while(x <= zsz){
 30         bit[x] += v;
 31         x += x & (-x);
 32     }
 33 }
 34 int query(int x){
 35     int ret = 0;
 36     while(x > 0){
 37         ret += bit[x];
 38         x -= x & (-x);
 39     }
 40     return ret;
 41 }
 42 bool cmp_x(Node & n1, Node & n2){
 43     if(n1.x != n2.x) return n1.x < n2.x;
 44     if(n1.y != n2.y) return n1.y < n2.y;
 45     if(n1.z != n2.z) return n1.z < n2.z;
 46     return n1.id < n2.id;
 47 }
 48 bool cmp_y(Node & n1, Node & n2){
 49     if(n1.y != n2.y) return n1.y < n2.y;
 50     if(n1.z != n2.z) return n1.z < n2.z;
 51     return n1.id < n2.id;
 52 }
 53 void cdq(int l, int r){
 54     if(l >= r) return ;
 55     int m = l+r >> 1;
 56     cdq(l, m); cdq(m+1, r);
 57     int k = 0;
 58     for(int i = l; i <= m; i++)
 59         if(!B[i].id) C[++k] = B[i];
 60     for(int i = m+1; i <= r; i++)
 61         if(B[i].id)  C[++k] = B[i];
 62     if(C[1].id != 0 || C[k].id == 0) return ;/// 剪枝
 63     sort(C+1, C+1+k, cmp_y);
 64     for(int i = 1; i <= k; i++){
 65         if(C[i].op)
 66             ans[C[i].id] += query(C[i].z) * C[i].op;
 67         else
 68             add(C[i].z, 1);
 69     }
 70     for(int i = 1; i <= k; i++){
 71         if(C[i].op);
 72         else add(C[i].z, -1);
 73     }
 74 }
 75 void CDQ(int l, int r){
 76     if(l == r) return ;
 77     int m = l+r >> 1;
 78     CDQ(l,m); CDQ(m+1,r);
 79     int k = 0;
 80     for(int i = l; i <= m; i++)
 81         if(!A[i].id)  B[++k] = A[i];
 82     for(int i = m+1; i <= r; i++)
 83         if(A[i].id)   B[++k] = A[i];
 84     if(B[1].id != 0 || B[k].id == 0) return ;/// 剪枝
 85     sort(B+1, B+1+k, cmp_x);
 86     cdq(1,k);
 87 }
 88 
 89 inline void nownode(int x, int y, int z, int op, int id){
 90     ++tot; A[tot].x = x; A[tot].y = y; zz[tot] = z;
 91     A[tot].z = z; A[tot].op = op; A[tot].id = id;
 92 }
 93 int main(){
 94     int T;
 95     scanf("%d", &T);
 96     while(T--){
 97         int n, op, x1, y1, z1, x2, y2, z2, m = 0;
 98         tot = 0;
 99         scanf("%d", &n);
100         for(int i = 1; i <= n; i++){
101             scanf("%d", &op);
102             if(op == 1){
103                 scanf("%d%d%d", &x1, &y1, &z1);
104                 nownode(x1, y1, z1, 0, 0);
105             }
106             else {
107                 m++;
108                 ans[m] = 0;
109                 scanf("%d%d%d", &x1, &y1, &z1);
110                 scanf("%d%d%d", &x2, &y2, &z2);
111                 nownode(x2,y2,z2,1,m);
112                 nownode(x1-1,y1-1,z2,1,m);
113                 nownode(x2,y1-1,z2,-1,m);
114                 nownode(x1-1,y2,z2,-1,m);
115 
116                 nownode(x2,y2,z1-1,-1,m);
117                 nownode(x1-1,y1-1,z1-1,-1,m);
118                 nownode(x2,y1-1,z1-1,1,m);
119                 nownode(x1-1,y2,z1-1,1,m);
120             }
121         }
122         sort(zz+1, zz+tot+1);
123         zsz = unique(zz+1, zz+tot+1) - zz - 1;
124         for(int i = 1; i <= tot; i++)
125             A[i].z = lower_bound(zz+1, zz+1+zsz, A[i].z) - zz;
126         CDQ(1, tot);
127         for(int i = 1; i <= m; i++)
128             printf("%d\n", ans[i]);
129     }
130     return 0;
131 }
View Code

 

转载于:https://www.cnblogs.com/MingSD/p/9869522.html

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

智能推荐

神经网络与机器学习 笔记—基本知识点(下)_TK13的博客-程序员宅基地_神经网络先验知识是什么

神经网络与机器学习笔记—基本知识点(下)0.1网络结构: 神经网络中神经元的构造方式与用于训练网络的学习算法有着密切的联系,有三种基本的网络结构:0.7知识表示: 知识就是人或机器存储起来以备使用的信息或模型,用来对外部世界作出解释、预测和适当的反应。主要特征: ...

Spark(八) -- 百亿级大数据实时计算实战 Spark Streaming对接Kafka_众里寻她千百回的博客-程序员宅基地

Spark Streaming整合Kafka1.1 Kafka快速回顾1.1.1 核心概念图解Broker : 安装Kafka服务的机器就是一个brokerProducer :消息的生产者,负责将数据写入到broker中(push)Consumer:消息的消费者,负责从kafka中拉取数据(pull),老版本的消费者需要依赖zk,新版本的不需要Topic: 主题,相当于是数据的一个分类,不同topic存放不同业务的数据 --主题:区分业务Replication:副本,数据保存多少份(保证

Docker快速安装RabbitMQ服务_星河_赵梓宇的博客-程序员宅基地

 Docker快速安装RabbitMQ服务 快速开始#!/bin/bash# 建议保存为start.sh脚本执行docker run -d --hostname my-rabbit --name some-rabbit --restart always -p 15672:15672 -e RABBITMQ_DEFAULT_USER=user -e RABBITMQ_DEFAU...

傅里叶变换(时域频域)_kalp_yp的博客-程序员宅基地_时域频域变换公式

我保证这篇文章和你以前看过的所有文章都不同,这是 2012 年还在果壳的时候写的,但是当时没有来得及写完就出国了……于是拖了两年,嗯,我是拖延症患者……这篇文章的核心思想就是:要让读者在不看任何数学公式的情况下理解傅里叶分析。傅里叶分析不仅仅是一个数学工具,更是一种可以彻底颠覆一个人以前世界观的思维模式。但不幸的是,傅里叶分析的公式看起来太复杂了,所以很多大一新生上来就懵圈并从此对...

QT 语言家使用 vs2010+QT5.2.1_雨夜拂晓的博客-程序员宅基地

一、介绍一下QM文件与TS文件与作用与联系。     QM文件是QT中translate类进行读取的源文件(英译中的翻译文件),其代码是不可读懂的。      TS文件的生成:       Ludpdata   xx.pro.     TS文件其格式是XML的,可以通过编译器进行编辑。     它们的联系:             

从源码编译安装CMake 3.17.1_stayreal1994的博客-程序员宅基地

文章目录起因:为什么要从源码编译安装cmake?方法1. 从官网下载源码、解压2. 删除旧版CMake3. 编译结果起因:为什么要从源码编译安装cmake?笔者在编译gRPC相关项目时,gRPC官方要求cmake版本必需满足cmake&gt;=3.13,然而我使用apt能获取到的最新版本为3.11,此时cmake官网版本已经到了3.17.3。并且由于笔者是在树莓派上使用cmake,官网上编译...

随便推点

修改tomcat运行窗口的title_陈家小少的博客-程序员宅基地_tomcat bat titile

修改catalina.bat文件在catalina.bat文件中搜索“TITLE”找到如下代码:修改后直接启动Tomcat就可以了,效果如下:

WriteProfileString 函数 , WritePrivateProfileString 函数, WritePrivateProfileStruct 函数_chinabinlang的博客-程序员宅基地

WriteProfileString 函数:背景:   调用了WriteProfileString, 却不知道该配置信息到底是注册表中,还是在INI文件中. 经过在网上查询, 在windows的目录下找到与程序名同名的INI文件.原因: 1/调试跟踪到CWinApp::WriteProfileString中间,发现了这个函数:return ::WritePrivateProfi

windows下安装mathtype公式编辑器记录_点灯小能手的博客-程序员宅基地_windows公式编辑器

文章目录1 软件下载2 软件安装1 软件下载使用搜索引擎搜索MathType,进入MathType官网,找到免费试用点击免费试用后进入下载界面,将软件下载到本地2 软件安装安装前先关闭office软件(word\excel\powerpoint),然后双击安装包没有购买产品密钥,直接试用30天修改安装目录到D盘安装完成。...

python设置utf8编码_如何在Python中打印UTF-8编码的文本到控制台3?_weixin_39649660的博客-程序员宅基地

I'm running a recent Linux system where all my locales are UTF-8:LANG=de_DE.UTF-8LANGUAGE=LC_CTYPE="de_DE.UTF-8"LC_NUMERIC="de_DE.UTF-8"LC_TIME="de_DE.UTF-8"...LC_IDENTIFICATION="de_DE.UTF-8"LC_ALL=No...

论文阅读:From Distributed Machine Learning to Federated Learning: A Survey_三金samkam的博客-程序员宅基地

论文名字 From Distributed Machine Learning to Federated Learning: A Survey 来源 年份 2021.4.29 作者 Ji Liu, Jizhou Huang, Yang Zhou, Xuhong Li, Shilei Ji, Haoyi Xiong, Dejing Dou 核心点 ...

CAP 定理的含义_awesome_go的博客-程序员宅基地_cap技术并说明其含义

分布式系统(distributed system)正变得越来越重要,大型网站几乎都是分布式的。分布式系统的最大难点,就是各个节点的状态如何同步。CAP 定理是这方面的基本定理,也是理解分布式系统的起点。本文介绍该定理。它其实很好懂,而且是显而易见的。下面的内容主要参考了 Michael Whittaker 的文章。一、分布式系统的三个指标1998年,加州大学的计算机科学家 Er...

推荐文章

热门文章

相关标签