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

10.3 闲话-分散层叠

10.3 闲话-分散层叠

这个东西好像没什么用,但是好像有有些用。

先看这么个问题:

给定 \(k\) 个长度为 \(n\) 的序列,\(m\) 次询问,每次询问 \(x\)\(k\) 个序列中的后继的异或和,强制在线

这东西有个显然的 \(O(mk\log n)\) 做法,但是我们可以寻求更优秀的算法。

分散层叠维护的就是这么个东西。

分散层叠需要维护一个数组 \(M_{i,j}\) 其中有三个值 \(\{val, now, nxt\}\) 分别表示值,该序列后继位置,\(M_{i+1}\) 中后继位置。

但是这时直接跳肯定假了,为啥?

因为前面可能还有合法的点呢,那么可以每隔一个将 \(M_{i+1}\) 中的元素插入 \(M_{i}\) 中,这是维护的 \(nxt\) 就是这写插入点中的后继位置了。

这时跳下去竟然合法点只有 \(nxt, nxt-1\) 两个点,为啥?

因为 \(nxt - 2\) 一定在 \(M_{i}\) 可是我们没有找到它,那么它就一定不是后继。

使用归并排序维护,查询先二分出 \(M_1\) 的位置。

复杂度 \(O(m(k+\log n))\),空间复杂度 \(O(2n)\)

这个分散层叠十分深刻的一点是它其实维护的是一个 \(DAG\) 结构,所以支持 \(DAG\) 上的链查询。

还有就是为什么要隔一个插一个,其实可以隔 \(p\) 个,这是也是没有问题的,可以做到时空复杂度平衡。

这东西可以做一些大分块,比如第十分块加强版。

可以分块后每个块维护分散层叠,能做到 \(O(n\sqrt{n\log n})\),线段树底层分块加分散层叠做到 \(O(n\sqrt n)\)

修改暴力重构就行。

http://www.hskmm.com/?act=detail&tid=23811

相关文章:

  • 博客园实验1
  • arm汇编
  • 模型与分词器
  • subclipse最新版本更新地址
  • 板子2
  • 从DQN到Double DQN:分离动作选择与价值评估,解决强化学习中的Q值过估计问题
  • P9877/QOJ5069 Vacation
  • CF1916G Optimizations From Chelsu
  • 详细介绍:微服务架构:基于Spring Cloud ,构建同城生活服务平台
  • 云锵投资 2025 年 9 月简报
  • 【游记】北京师范大学讲课
  • 字符串Hash
  • 详细介绍:代码世界的“数字刑侦”:深入解析代码审计实战
  • 三霍尔BLDC如何测量Hall同步角度(需要示波器)
  • QBXT2025S刷题 Day2
  • PyCharm中搭建PyTorch和YOLOv10开发环境 - 实践
  • 基于PCIe(XDMA)的多路(1-32路)信号采集与回放子系统, 多路视频、AD、光纤等信号,支持PR over PCIe
  • Spring事务管理:@Transactional注解
  • AI元人文的未来:软硬件协同发展研究报告——声明Ai研究
  • 个人主页网址
  • 10.3考试t3(similarity)solution
  • 安卓渗透测试流
  • 日志|寻找旋转排序数组中的最小值|寻找两个正序数组的中位数|二分查找
  • 有关三角剖分的性质
  • 西门子通信-自制示意
  • Vue之刷新页面会触发的生命周期函数
  • 傅里叶的一生
  • Dos命令学习(新手)
  • 吴恩达深度学习课程一:神经网络和深度学习 第一周:深度学习简介
  • 实用指南:AI Agent开发平台如何设计?核心架构与工作流实战案例详解