当前位置: 首页 > news >正文

【每日一题】补档 ABC309F - Box in Box | 三维偏序 | 树状数组 | 中等

题目内容

原题链接

给定 n n n 个箱子,问是否存在一个箱子 x x x 是否可以放到另一个箱子 y y y 里。
需要满足 h x < h y , w x < w y , d x < d y h_x<h_y,w_x<w_y,d_x<d_y hx<hy,wx<wy,dx<dy
箱子可以随意翻转。

数据范围

1 ≤ n ≤ 2 ⋅ 1 0 5 1\leq n\leq 2\cdot 10^5 1n2105
1 ≤ h i , w i , d i ≤ 1 0 9 1\leq h_i,w_i,d_i\leq 10^9 1hi,wi,di109

题解

首先按从小到大对 h , w , d h,w,d h,w,d 进行排序。

这里假设对所有的箱子,排序后都有 h ≤ w ≤ d h\leq w\leq d hwd

那么我们再按照 h h h 为第一关键字, w w w 为第二关键字, d d d 为第三关键字对箱子进行从小到大的排序。

然后我们从按 h h h 从小到大枚举,每次将所有 h h h 相同的箱子一起枚举。

这样,我们就可以对剩下的 w w w d d d 构建树状数组了。

对于箱子 i i i ,找到 h j < h i h_j<h_i hj<hi j j j ,且 w j < w i w_j<w_i wj<wi 的最小的 d j d_j dj 。判断 d j < d i d_j < d_i dj<di 是否成立即可。

然后在判断完后,将所有值为 h i h_i hi 的箱子都加入到树状数组中。

q u e r y ( p ) query(p) query(p) 其实是在求 w ≤ p w\leq p wp 的最小的 d d d

这个问题又叫三维偏序。

时间复杂度: O ( n log ⁡ n ) O(n\log n) O(nlogn)

代码

#include <bits/stdc++.h>
using namespace std;const int INF = 0x3f3f3f3f;struct Node {int a[3];
};int main()
{ios::sync_with_stdio(false);cin.tie(nullptr);int n;cin >> n;vector<Node> vec(n);for (int i = 0; i < n; ++i) {for (int j = 0; j < 3; ++j) cin >> vec[i].a[j];sort(vec[i].a, vec[i].a + 3);}sort(vec.begin(), vec.end(), [](const Node& A, const Node& B) {return A.a[0] < B.a[0];});vector<int> b;for (int i = 0; i < n; ++i) b.push_back(vec[i].a[1]);sort(b.begin(), b.end());b.erase(unique(b.begin(), b.end()), b.end());auto get = [&](int x) {return int(lower_bound(b.begin(), b.end(), x) - b.begin() + 1);};for (int i = 0; i < n; ++i) vec[i].a[1] = get(vec[i].a[1]);int m = int(b.size());vector<int> tr(m + 1, INF);auto update = [&](int p, int x) {while (p <= m) {tr[p] = min(tr[p], x);p += (p & -p);}};auto query = [&](int p) {int res = INF;while (p >= 1) {res = min(res, tr[p]);p -= (p & -p);}return res;};bool ok = false;for (int i = 0; i < n; ++i) {int j = i + 1;while (j < n && vec[j].a[0] == vec[i].a[0]) j += 1;// 找到是否存在这么一个即可for (int k = i; k < j; ++k) {if (query(vec[k].a[1] - 1) < vec[k].a[2]) {ok = true;break;}}if (ok) break;// 把当前的部分全部添加进去for (int k = i; k < j; ++k) {update(vec[k].a[1], vec[k].a[2]);}i = j - 1;}if (ok) cout << "Yes\n";else cout << "No\n";return 0;
}

相关文章:

【每日一题】补档 ABC309F - Box in Box | 三维偏序 | 树状数组 | 中等

题目内容 原题链接 给定 n n n 个箱子&#xff0c;问是否存在一个箱子 x x x 是否可以放到另一个箱子 y y y 里。 需要满足 h x < h y , w x < w y , d x < d y h_x<h_y,w_x<w_y,d_x<d_y hx​<hy​,wx​<wy​,dx​<dy​。 箱子可以随意翻转。 …...

异步编程 - 13 高性能线程间消息传递库 Disruptor

文章目录 Disruptor概述Disruptor中的核心术语Disruptor 流程图 Disruptor的特性详解基于Disruptor实现异步编程 Disruptor概述 Disruptor是一个高性能的线程间消息传递库&#xff0c;它源于LMAX对并发性、性能和非阻塞算法的研究&#xff0c;如今构成了其Exchange基础架构的核…...

(DXE_DRIVER)PciHostBridge

UEFI-PciHostBridge 1、PciHostBridge简介 PciHostBridge: 提供PCI配置空间,IO,MEM空间访问接口以及统一维护平台相关的PCI资源,提供gEfiPciHostBridgeResourceAllocationProtocolGuid,创建RootBridge等为PciBusDxe提供服务; 2、PciHostBridge 配置空间 PCI桥可管理其下PCI子…...

SpringMVC的增删改查的案例

目录 前言&#xff1a; 1.总体思路&#xff1a; 2.前期准备 3.前台页面 前言&#xff1a; 我们今天来学习研究SpringMVC的增删改查&#xff0c;希望这篇博客能够帮助正在学习&#xff0c;工作的你们&#xff01;&#xff01;&#xff01; 1.总体思路&#xff1a; 首先我们得…...

golang入门笔记——nginx

文章目录 Nginx介绍Nginx的安装Nginx文件Nginx反向代理负载均衡nginx动静分离URLRewrite防盗链nginx高可用配置安全性Nginx限流Nginx缓存集成Lua脚本OpenRestry Nginx介绍 Nginx是一个高性能的HTTP和反向代理服务器&#xff0c;特点是占用内存少&#xff0c;并发能力强&#x…...

最新报告!TikTok 市场小家电大商机,GMV破亿的爆款如何复制?

近期&#xff0c;新锐小家电品牌Gaabor空气炸锅在东南亚卖爆了&#xff0c;单款商品GMV短时间内突破两亿&#xff0c;在印尼、泰国、马来西亚、菲律宾、越南均开设本土TikTok 小店&#xff0c;增长势头还在持续。 但Gaabor并不是个例。 整个东南亚家电市场规模增长迅速&#…...

功能定义-紧急制动系统

功能简介 紧急制动系统的触发过程如上图所示&#xff1a; 安全距离报警&#xff1a;当两车距离较近时&#xff0c;会给予驾驶员相应提示 预报警&#xff1a;当两车存在碰撞风险但风险较低【Danger Level1】时&#xff0c;会给予驾驶员提示【提示相比之前更为明显】 制动预填充&…...

Map与Set的区别

map与set是一种进行搜索的数据结构。 一 Map map存储的是key-value的键值对。 1 map中的常见方法 方法作用put(key,value)向map中存放key-value键值对get(key)根据key值得到value值getOrDefault(key,value)获取值为key的value&#xff0c;若不存在&#xff0c;则将key值对应…...

基于uwb和IMU融合的三维空间定位算法matlab仿真

目录 1.算法运行效果图预览 2.算法运行软件版本 3.部分核心程序 4.算法理论概述 5.算法完整程序工程 1.算法运行效果图预览 2.算法运行软件版本 matlab2022a 3.部分核心程序 ..........................................................................kkk 0; for E…...

Visual Studio 2019下使用C++与Python进行混合编程——环境配置与C++调用Python API接口

前言 在vs2019下使用C与Python进行混合编程,在根源上讲&#xff0c;Python 本身就是一个C库&#xff0c;那么这里使用其中最简单的一种方法是把Python的C API来嵌入C项目中&#xff0c;来实现混合编程。当前的环境是&#xff0c;win10,IDE是vs2019,python版本是3.9&#xff0c…...

STM32F4X RTC

STM32F4X RTC 什么是RTCSTM32F4X RTCSTM32F4X RTC框图STM32F4X RTC计数频率STM32F4X RTC日历STM32F4X RTC闹钟 STM32F4X RTC例程 什么是RTC RTC全程叫Real-Time Clock实时时钟&#xff0c;是MCU中一个用来计时的模块。RTC的一个主要作用是用来显示实时时间&#xff0c;就像日常…...

[git] 如何克隆仓库,进行项目撰写,并绑定自己的远程仓库

摘要&#xff1a;删除.git文件&#xff0c;才可重新绑定远程仓库。 具体步骤&#xff1a; 文件夹右键&#xff0c;进入”Git Bash Here“执行命令 1. 执行 ”git clone 仓库地址“&#xff0c;克隆仓库 2. 在生成的仓库中&#xff0c;删除 .git 文件 3. git init 初始化仓库…...

【C++】模拟实现二叉搜索树的增删查改功能

个人主页&#xff1a;&#x1f35d;在肯德基吃麻辣烫 我的gitee&#xff1a;C仓库 个人专栏&#xff1a;C专栏 文章目录 一、二叉搜索树的Insert操作&#xff08;非递归&#xff09;分析过程代码求解 二、二叉搜索树的Erase操作&#xff08;非递归&#xff09;分析过程代码求解…...

Yolov8-pose关键点检测:模型轻量化创新 | ScConv结合c2f | CVPR2023

💡💡💡本文解决什么问题:ScConv(空间和通道重建卷积),一个即插即用的架构单元,可以可以直接用来替代各种卷积神经网络中的标准卷积。 ScConv | GFLOPs从9.6降低至9,参数量从6482kb降低至6479kb Yolov8-Pose关键点检测专栏介绍:https://blog.csdn.net/m0_637742…...

【洛谷 P1060】[NOIP2006 普及组] 开心的金明 题解(动态规划+01背包)

[NOIP2006 普及组] 开心的金明 题目描述 金明今天很开心&#xff0c;家里购置的新房就要领钥匙了&#xff0c;新房里有一间他自己专用的很宽敞的房间。更让他高兴的是&#xff0c;妈妈昨天对他说&#xff1a;“你的房间需要购买哪些物品&#xff0c;怎么布置&#xff0c;你说…...

什么是CI/CD:持续集成与持续交付?(InsCode AI 创作助手)

在现代软件开发领域&#xff0c;CICD&#xff08;Continuous Integration and Continuous Delivery&#xff09;是一种关键性的开发实践&#xff0c;它有助于提高软件交付的质量和效率。本文将深入探讨CICD的定义、原理和重要性&#xff0c;以及如何在项目中实施CICD流程。 什…...

redis 高可用

Redis 高可用 在web服务器中&#xff0c;高可用是指服务器可以正常访问的时间&#xff0c;衡量的标准是在多长时间内可以提供正常服务&#xff08;99.9%、99.99%、99.999%等等&#xff09;。 但是在Redis语境中&#xff0c;高可用的含义似乎要宽泛一些&#xff0c;除了保证提供…...

什么样的词条可以创建维基百科?

维基百科在国内用得比较少&#xff0c;有一些特殊原因&#xff0c;维基百科的控制权海外&#xff0c;目前维基百科和谷歌是一样的&#xff0c;在国内是无法正常访问的。但做海外推广的朋友都是知道维基百科的&#xff0c;小马识途营销顾问认为它在世界互联网领域的地位&#xf…...

poll epoll初学习

正是select这些缺点&#xff0c;才有了poll 1.I/O多路转接之poll 2.I/O多路转接之epoll 其中的struct epoll_event:...

BMS电池管理系统——电芯需求数据(三)

BMS电池管理系统 文章目录 BMS电池管理系统前言一、有什么基础数据二、基础数据分析1.充放电的截至电压2.SOC-OCV关系表3.充放电电流限制表4.充放电容量特性5.自放电率 总结 前言 在新能源产业中电芯的开发也占有很大部分&#xff0c;下面我们就来看一下电芯的需求数据有哪些 …...

第19节 Node.js Express 框架

Express 是一个为Node.js设计的web开发框架&#xff0c;它基于nodejs平台。 Express 简介 Express是一个简洁而灵活的node.js Web应用框架, 提供了一系列强大特性帮助你创建各种Web应用&#xff0c;和丰富的HTTP工具。 使用Express可以快速地搭建一个完整功能的网站。 Expre…...

Map相关知识

数据结构 二叉树 二叉树&#xff0c;顾名思义&#xff0c;每个节点最多有两个“叉”&#xff0c;也就是两个子节点&#xff0c;分别是左子 节点和右子节点。不过&#xff0c;二叉树并不要求每个节点都有两个子节点&#xff0c;有的节点只 有左子节点&#xff0c;有的节点只有…...

分布式增量爬虫实现方案

之前我们在讨论的是分布式爬虫如何实现增量爬取。增量爬虫的目标是只爬取新产生或发生变化的页面&#xff0c;避免重复抓取&#xff0c;以节省资源和时间。 在分布式环境下&#xff0c;增量爬虫的实现需要考虑多个爬虫节点之间的协调和去重。 另一种思路&#xff1a;将增量判…...

使用 SymPy 进行向量和矩阵的高级操作

在科学计算和工程领域&#xff0c;向量和矩阵操作是解决问题的核心技能之一。Python 的 SymPy 库提供了强大的符号计算功能&#xff0c;能够高效地处理向量和矩阵的各种操作。本文将深入探讨如何使用 SymPy 进行向量和矩阵的创建、合并以及维度拓展等操作&#xff0c;并通过具体…...

20个超级好用的 CSS 动画库

分享 20 个最佳 CSS 动画库。 它们中的大多数将生成纯 CSS 代码&#xff0c;而不需要任何外部库。 1.Animate.css 一个开箱即用型的跨浏览器动画库&#xff0c;可供你在项目中使用。 2.Magic Animations CSS3 一组简单的动画&#xff0c;可以包含在你的网页或应用项目中。 3.An…...

Linux nano命令的基本使用

参考资料 GNU nanoを使いこなすnano基础 目录 一. 简介二. 文件打开2.1 普通方式打开文件2.2 只读方式打开文件 三. 文件查看3.1 打开文件时&#xff0c;显示行号3.2 翻页查看 四. 文件编辑4.1 Ctrl K 复制 和 Ctrl U 粘贴4.2 Alt/Esc U 撤回 五. 文件保存与退出5.1 Ctrl …...

【LeetCode】3309. 连接二进制表示可形成的最大数值(递归|回溯|位运算)

LeetCode 3309. 连接二进制表示可形成的最大数值&#xff08;中等&#xff09; 题目描述解题思路Java代码 题目描述 题目链接&#xff1a;LeetCode 3309. 连接二进制表示可形成的最大数值&#xff08;中等&#xff09; 给你一个长度为 3 的整数数组 nums。 现以某种顺序 连接…...

MeshGPT 笔记

[2311.15475] MeshGPT: Generating Triangle Meshes with Decoder-Only Transformers https://library.scholarcy.com/try 真正意义上的AI生成三维模型MESHGPT来袭&#xff01;_哔哩哔哩_bilibili GitHub - lucidrains/meshgpt-pytorch: Implementation of MeshGPT, SOTA Me…...

Qt Quick Controls模块功能及架构

Qt Quick Controls是Qt Quick的一个附加模块&#xff0c;提供了一套用于构建完整用户界面的UI控件。在Qt 6.0中&#xff0c;这个模块经历了重大重构和改进。 一、主要功能和特点 1. 架构重构 完全重写了底层架构&#xff0c;与Qt Quick更紧密集成 移除了对Qt Widgets的依赖&…...

【动态规划】B4336 [中山市赛 2023] 永别|普及+

B4336 [中山市赛 2023] 永别 题目描述 你做了一个梦&#xff0c;梦里有一个字符串&#xff0c;这个字符串无论正着读还是倒着读都是一样的&#xff0c;例如&#xff1a; a b c b a \tt abcba abcba 就符合这个条件。 但是你醒来时不记得梦中的字符串是什么&#xff0c;只记得…...