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

并非传统意义上的整体二分

是的,如标题所见,本文章会以作者所理解的整体二分思想来介绍一系列整体二分食用方法。

一下内容均是作者本人理解,可能会与算法本身冲突。

1 本质

1.1 板子及从中的启发

我们在做主席树板子的时候,如果使用整体二分,我们将序列 A A A 与查询的 l l l r r r 打包丢到整体二分这个分治结构上去时,会发现,他就类似于一个值域线段树,每一个根节点都有一个树状数组,当满足 a i ≤ m i d a_i \leq mid aimid 时该值的下表 + 1 +1 +1,这也就变成了一个在未可持久化的权值线段树上二分。当然这只是 n l o g 2 n nlog^2n nlog2n 的做法,当然还有 n l o g n nlogn nlogn 的做法。我们会发现树状数组完全是可以省略掉的,注意到树状数组的修改总是在查询操作前停止,所以我们可以再查询之前将递归到此的序列先用前缀和,再查询,他并不会影响答案。

最后我们会发现若需在线,我们仅需将当前的每个子树的根节点上动态存在的树状数组用平衡树存下来,就可以在使用 n l o g n nlogn nlogn 的空间下完成在线。(此空间当限此题)

2 运用

2.1 三维偏序

所以有了这个近似于树套树的一个理解,我们就可以将他拿去写偏序题目,如:三维偏序(陌上开花)。那这该怎么进行操作呢?

首先排序去掉一维,其次我们可以通过上述的类权值线段树的结构查找小于等于第二维的那些子树的根节点,再去查找记录了这些根节点的树状数组所存储的子树内的序列元素的第三维(以他们第三维为下标并 + 1 +1 +1),然后再在每个树状数组查询小于等于第三维的个数。这样就结束了朴素的三维偏序。

2.2 三维偏序带二分

那为什么,我会将其称之为朴素?

区间 mex

给出了答案。

我们需要在整体二分类权值线段树这个结构上二分,而树状数组在这个子树维护的元素 L L L R R R 中,每个元素的个数是否不为 0。

这显然是一个带着三维偏序条件的二分。

2.3

构造具有单调性的序列,这个就应该不需要多说了吧,显然当成 N N N 次二分,check 为贪心。

3 拓展

那么在刚开始所介绍的在线方法,是为 此题 的写法做了一个铺垫。

显然 dp 转移是一个三维偏序,但是若用整体二分进行转移会发现当求解 d p i dp_i dpi 时,我们需要得到 [ 1 , i − 1 ] [1,i-1] [1,i1] 这个区间的所有 dp 值,所以需要在线处理。

那么显然我们可以将原本三维偏序板子代码中的树状数组改成平衡树,在加上一个修改,这就结束了。

十分的简单呀。

但是为什么会说空间复杂度要单独考虑。

思考一个问题:如果是查多次全局第 k k k 呢?

那么显然树状数组就变成的一个变量,那么在线也只需要一个变量。(这不是就真的成了值域线段树了吗……)

另外有一种做法,我感觉像 cdq 就没写进来,就先这样结束吧。

以上题目我的题解:

  1. 三维偏序
  2. mex
  3. 序列

应该会比这个文章详细一点。

感觉自己写的好抽象啊

相关文章:

并非传统意义上的整体二分

是的,如标题所见,本文章会以作者所理解的整体二分思想来介绍一系列整体二分食用方法。 一下内容均是作者本人理解,可能会与算法本身冲突。 1 本质 1.1 板子及从中的启发 我们在做主席树板子的时候,如果使用整体二分&#xff0…...

PostgreSQL的一主一从集群搭建部署 (同步)

一、实验环境 虚拟机名IP身份简称keep-postgres12-node1192.168.122.87主节点node1keep-postgres12-node2192.168.122.89备节点node2 二、安装数据库 源码包方式(主) 1、创建用户 [rootkeep-postgres12-node1 ~]# groupadd postgres [rootkeep-post…...

ios逆向某新闻 md5+aes

本期的案例比较简单,也许是ios逆向算法本来就比较简单的原因,所以前面我就多扯一些爬虫和逆向的东西。之前写的文章都是js逆向和android逆向的案例,这也是首篇ios的案例,所以会从入门开始讲起。 3大逆向对比 首先爬虫工程师大部…...

grpc的负载均衡

grpc的负载均衡分为client-side load balance和server-side load balance。 所谓的“客户端负载均衡”是指主调方调用被调方的时候,在grpc.DialContext里需要指定grpc.WithDefaultServiceConfig,这个DefaultServiceConfig默认是用pick-first策略。也支持…...

提升搜索体验!—— 推出 Elastic Rerank 模型(技术预览版)

作者:来自 Elastic Shubha Anjur Tupil 几分钟内即可开始使用 Elastic Rerank 模型:强大的语义搜索功能,无需重新索引,提供灵活性和成本控制;高相关性、顶级性能和文本搜索效率。 使用我们全新的先进跨编码器 Elastic …...

【51单片机】程序实验1112.外部中断-定时器中断

主要参考学习资料:B站【普中官方】51单片机手把手教学视频 前置知识:C语言 单片机套装:普中STC51单片机开发板A4标准版套餐7 码字不易,求点赞收藏加关注(•ω•̥) 有问题欢迎评论区讨论~ 目录 程序实验11&12.外部中断-定时器…...

webrtc-java:引领Java进入实时通信新时代

webrtc-java:引领Java进入实时通信新时代 项目地址:https://gitcode.com/gh_mirrors/we/webrtc-java 在现代互联网应用中,实时通信(Real-Time Communication, RTC)已成为连接人们的桥梁。而说起RTC技术的先锋,不得不…...

TongWeb7-东方通快速使用手册

TongWeb7-东方通 快速使用手册 文章目录 第1章 TongWeb7 产品介绍 1.1 概述1.2 规范支持 第2章 TongWeb7 安装 2.1 TongWeb7 安装要求 2.1.1 TongWeb7 支持的操作系统2.1.2 系统要求2.1.3 其他 2.2 安装TongWeb72.3TongWeb7 目录结构说明2.4 TongWeb7 的启动和停止 第3章 应用…...

JVM内存区块

大家好,经过前两篇文章的介绍,大家对数组也有了一定了解,其实所有的数组都是对象,我们在方法中引用数组的变量叫做引用变量(简称引用),那么数组到底是存放在哪里的呢,为什么引用再出…...

C语言单元总结

黑色加粗表示刷题刷到这样的题 红色加粗表示可能重要 单元一 程序设计宏观认识 C语言程序框架 C语言程序最基本的程序框架由两部分构成,分别是 1) 编译预处理 2) 函数组 C语言程序构成 C程序最大的特点就是所有的程序都是用函数来装配的,函数是构成…...

通过PS和Unity制作2D动画之一:创建形象

1、通过路径画出轮廓 使用路径的过程中,需要注意: 1)如果使用形状工具作图,比如使用椭圆工具画正圆形,需要设置其属性为“路径”。 2)使用路径选择工具,再按住Alt键点击某个路径,可…...

Notable是一款优秀开源免费的Markdown编辑器

一、Notable简介 ‌ Notable‌是一款开源的跨平台Markdown编辑器,支持Linux、MacOS、Windows以及国产操作系统等多种主流操作系统。它以其高颜值和强大的功能,成为了许多用户的首选工具。 主要特性 实时预览‌: Notable提供了实时预览功能&…...

基于MFC绘制门电路

MFC绘制门电路 1. 设计内容、方法与难点 本课题设计的内容包括了基本门电路中与门和非门的绘制、选中以及它们之间的连接。具体采用的方法是在OnDraw函数里面进行绘制,并设计元器件基类,派生出与门和非门,并组合了一个引脚类,在…...

C—指针初阶(2)

如果看完阁下满意的话,能否一键三连呢,我的动力就是大家的支持与肯定,冲! 二级指针 我们先看概念以及作用:用来存放一级指针的地址的指针 先看例子,我们逐一分析 我们先分析上面那个“1” 标注那里&#x…...

Linux 基础环境的开发工具以及使用(下)

1. make / Makefile 自动化构建的工具 1)引入 在我们进行一些大型的工程的时候,代码量是极其大,当我们代码在进行一系列的编译的时候,难免会出现一些错误,当我们对错误进行一系列的更改之后,难道我们需要…...

constexpr、const和 #define 的比较

constexpr、const 和 #define 的比较 一、定义常量 constexpr 定义:constexpr用于定义在编译期可求值的常量表达式。示例:constexpr int x 5;这里,x的值在编译期就确定为5。 const 定义:const表示变量在运行期间不能被修改&…...

期末复习-Hadoop综合复习

说明 以下内容仅供参考,提到不代表考到,请结合实际情况自己复习 目录 说明 一、题型及分值 二、综合案例题-部署Hadoop集群 或 部署Hadoop HA集群 案例 1:Hadoop 基础集群部署 案例 2:Hadoop HA 集群部署 案例 3&#xff…...

禁用SAP Hana错误密码锁定用户功能

背景 公司项目适配多种数据库其中包含SAP Hana,由于有同事的数据库连接工具保存了某个在用的数据库的旧密码,导致时不时会被锁用户。通过查询官方文档已解决,这里统一记录一下。 禁用密码锁定方法 以下按系统管理员和普通用户的解法分别列…...

Ubuntu 22.04加Windows AD域

说明:   Ubuntu 22.04系统通过realmd,sssd加入到 Active Directory 域,并为域用户配置sudo权限。同时为方便用户使用为Ubuntu系统安装wps与sogou中文输入法。 1. Ubuntu 22.04加入Windows AD域 1.1 首先配置网络,Ubuntu系统能…...

qt实现窗口的动态切换

先说一下整体思路。页面布局两个widget然后再将定时器和按钮关联起来。 定时器发出信号的时候,随着信号,不断地重新设置widget的宽度,实现窗口的动态切换。 具体操作如下: class QtWidgetsApplication4 : public QMainWindow {…...

XML Group端口详解

在XML数据映射过程中,经常需要对数据进行分组聚合操作。例如,当处理包含多个物料明细的XML文件时,可能需要将相同物料号的明细归为一组,或对相同物料号的数量进行求和计算。传统实现方式通常需要编写脚本代码,增加了开…...

Linux应用开发之网络套接字编程(实例篇)

服务端与客户端单连接 服务端代码 #include <sys/socket.h> #include <sys/types.h> #include <netinet/in.h> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <arpa/inet.h> #include <pthread.h> …...

idea大量爆红问题解决

问题描述 在学习和工作中&#xff0c;idea是程序员不可缺少的一个工具&#xff0c;但是突然在有些时候就会出现大量爆红的问题&#xff0c;发现无法跳转&#xff0c;无论是关机重启或者是替换root都无法解决 就是如上所展示的问题&#xff0c;但是程序依然可以启动。 问题解决…...

AI Agent与Agentic AI:原理、应用、挑战与未来展望

文章目录 一、引言二、AI Agent与Agentic AI的兴起2.1 技术契机与生态成熟2.2 Agent的定义与特征2.3 Agent的发展历程 三、AI Agent的核心技术栈解密3.1 感知模块代码示例&#xff1a;使用Python和OpenCV进行图像识别 3.2 认知与决策模块代码示例&#xff1a;使用OpenAI GPT-3进…...

Java如何权衡是使用无序的数组还是有序的数组

在 Java 中,选择有序数组还是无序数组取决于具体场景的性能需求与操作特点。以下是关键权衡因素及决策指南: ⚖️ 核心权衡维度 维度有序数组无序数组查询性能二分查找 O(log n) ✅线性扫描 O(n) ❌插入/删除需移位维护顺序 O(n) ❌直接操作尾部 O(1) ✅内存开销与无序数组相…...

python/java环境配置

环境变量放一起 python&#xff1a; 1.首先下载Python Python下载地址&#xff1a;Download Python | Python.org downloads ---windows -- 64 2.安装Python 下面两个&#xff0c;然后自定义&#xff0c;全选 可以把前4个选上 3.环境配置 1&#xff09;搜高级系统设置 2…...

【Oracle】分区表

个人主页&#xff1a;Guiat 归属专栏&#xff1a;Oracle 文章目录 1. 分区表基础概述1.1 分区表的概念与优势1.2 分区类型概览1.3 分区表的工作原理 2. 范围分区 (RANGE Partitioning)2.1 基础范围分区2.1.1 按日期范围分区2.1.2 按数值范围分区 2.2 间隔分区 (INTERVAL Partit…...

uniapp 集成腾讯云 IM 富媒体消息(地理位置/文件)

UniApp 集成腾讯云 IM 富媒体消息全攻略&#xff08;地理位置/文件&#xff09; 一、功能实现原理 腾讯云 IM 通过 消息扩展机制 支持富媒体类型&#xff0c;核心实现方式&#xff1a; 标准消息类型&#xff1a;直接使用 SDK 内置类型&#xff08;文件、图片等&#xff09;自…...

水泥厂自动化升级利器:Devicenet转Modbus rtu协议转换网关

在水泥厂的生产流程中&#xff0c;工业自动化网关起着至关重要的作用&#xff0c;尤其是JH-DVN-RTU疆鸿智能Devicenet转Modbus rtu协议转换网关&#xff0c;为水泥厂实现高效生产与精准控制提供了有力支持。 水泥厂设备众多&#xff0c;其中不少设备采用Devicenet协议。Devicen…...

嵌入式学习之系统编程(九)OSI模型、TCP/IP模型、UDP协议网络相关编程(6.3)

目录 一、网络编程--OSI模型 二、网络编程--TCP/IP模型 三、网络接口 四、UDP网络相关编程及主要函数 ​编辑​编辑 UDP的特征 socke函数 bind函数 recvfrom函数&#xff08;接收函数&#xff09; sendto函数&#xff08;发送函数&#xff09; 五、网络编程之 UDP 用…...