首页 > 其他分享 >数据结构只因屑化

数据结构只因屑化

时间:2023-12-14 12:11:25浏览次数:33  
标签:二分 外层 log 因屑化 复杂度 内层 数据结构 前缀

好像一直在做这个。
然而。。。。

越来越感觉这个东西不适合用来打 OI 了。
虽然还没有整出来。
只是用来确保复杂度还差不多。
也就是学术用途吧(?)


核心

大致的思想朴素而不完备。
主要适用于偏序类的东西,或者区间第 k 大之类的伪不可合并信息。

枚举每一维,整一个高维树套树。
对于单增/不带修的维,放至最外层。
对于这种情况可以考虑使用可持久化进行优化。
对于修改/查询不常规的,尽可能放至外层。

同时,为了确保空间复杂度,还需要结合连续段/虚树之类的技巧。
如果需要二分但是可供使用的复杂度不足一个 \(\log n\),那就考虑分散层叠优化。
这东西序列上能跑,树上也能跑。
或者是调换到外维。这个做法的题也遇到过。

另外,可以把这个过程转成分治实现。空间复杂度消掉好多。

然而,实际上仍然需要自行考虑很多问题。
上述框架只是废话。

整点题。看一看这东西是怎么随手整出来 500+ 的代码量的。


CTSC2008 网络管理

好好好,树链问题。
待修区间第 K 大。由于可合并所以树链本身不提供复杂度。
初步判定最后的时间复杂度应该是 \(O(n \log^2 n)\)。

树套树。外层是值,内层是位置。
那么空间复杂度判断为 \(O(n \log n)\)。
考虑我们查询的时候类似于二分答案,在外层树上查询。
因此,对于内层树,我们需要维护以下信息:

  1. 单点修改。
  2. 树链求和。

要求空间与有权点数成线性,时间不超过 \(O(\log n)\)。

这个自然是喜闻乐见的。
我们进行树上差分。将问题变成子树加,单点求值。
平衡树维护连续段,即可满足上述需求。

复杂度达成。
恭喜你收获巨大难打的待修线段树套平衡树维护连续段。

当然,把内层树改成线段树也可,但是空间会多一个 \(\log n\)。


还是上述问题。考虑改成分治。
显然,外层树就是个整体二分。
内层树是个喜闻乐见的虚树。
做完了。时间不变,空间线性。

整体二分套虚树前缀和。事实上我之前是打过类似的东西的。
提交记录。可以留意一下代码长度。
如果这是正式比赛那么最好注意一点了。


从拿到题到想到上述两个做法其实只需要 5min ~ 10min。
另外,我们暂时可以发现。

权值线段树 -> 整体二分。
序列线段树 -> CDQ 分治。
维护连续段 -> 虚树。

再来一个?


Camping Groups

题意转化完是板子。

首先是统计每个人做组长所能统治的人数。
这部分自行考虑。与主题无关。

接下来问题直接变成,区间 \([l, r]\) 内地位高于某个值的最大权值。
静态二维偏序。初步判断时间复杂度为 \(O(n \log n)\)。

由于区间最小值不可容斥,因此改成前缀最小值会更好处理一些。
因此,外层维护下标,内层维护地位值。
内层按照地位值从大到小排序,做前缀 \(\min\)。
发现内层需要二分。
不用分散层叠了,直接类划分树结构即可。

复杂度达成。时空同阶。

当然,就想外层维护权值内层维护位置也可。
把前缀 \(\min\) 改成线性 RMQ 就行了。
(真的有人会这么干吗)


转分治?
还是 CDQ,配上有序分裂 + 前缀 \(\min\) 即可。
这个自然是没什么难度的。


思考时间预计在 3min ~ 5min 之间。
相对来说这个题会好打一点。


鉴定为代码时间换思考时间。
这类东西基本上都有不动脑子的做法。
然而,你们 OI 就是喜欢考板子是吧。
(点名某些大型比赛)


今天本来看到了上面那个 CTSC 题,发现是个板子,准备打。
然后就胡出来一个树套树。
不甘心,转分治,更难打了。
索性跑路了。

这种只会胡题不会打题的毛病还没改啊。。。


你们 OI 什么时候才能扔掉 DS,多考点 ad-hoc 啊。

标签:二分,外层,log,因屑化,复杂度,内层,数据结构,前缀
From: https://www.cnblogs.com/-Houraisan-Kaguya/p/17900933.html

相关文章

  • Redis数据结构4:REDIS_ZIPLIST
    REDIS_ZIPLISTzipList(压缩列表)是一种紧凑型的数据结构,占用一片连续的内存,本质上是一个字节数组。能提高CPU缓存的利用效率,并且针对不同数据结构进行不同编码,节省内存开销。编码结构zipList的字节数组主要由5个部分组成:zlbytes、zltail、zllen、zltail和entry。zlbytes记录......
  • 数据结构:双链表
    由于双链表中大部分操作其实和单链表操作类似,所以这里只挑关键的一些函数1、定义与初始化typedefstructDNode{ElementTypedata;structDNode*prior,*next;}DNode,*DLinkList;boolInitialDLinkList(DLinkList&L){L=(DNode*)malloc(sizeof(DNode));......
  • 学习文件系统的数据结构
    学习文件系统的数据结构:深入理解计算机系统和操作系统运作的关键一步。以下是一份关于学习文件系统数据结构的学习总结,可能会帮助你系统地回顾所学的知识:inode(索引节点):1.inode是文件系统中非常重要的数据结构,它存储了文件的元数据,包括文件的大小、权限、拥有者等信息。2.理......
  • 数据结构---队列
    队列(Queue)是一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作。这种操作方式通常被称为FIFO(FirstInFirstOut,先进先出)。队列中的插入操作也被称为入队(enqueue),而删除操作则被称为出队(dequeue)。队列中的元素只能从一端(称为队头)添加......
  • 数据结构---栈
    栈(Stack)是一种线性数据结构,它按照后进先出(LIFO,LastInFirstOut)的原则存储和管理数据。这意味着最后一个被添加到栈中的元素将是第一个被移除的元素。栈的主要操作包括:压栈(Push):在栈的顶部添加一个元素。弹栈(Pop):移除栈顶部的元素。查看栈顶(Peek/Top):查看栈顶部的元素但不移除......
  • [持续更新][数据结构][算法]涵盖线性表、栈、链表、队列、图、动态规划、分治递归、回
    备考考点整理内部排序表格树的主要考点二叉树的常考紧紧抓住\(n_0=n_2+1\)\(n=n_0+n_1+n_2...n_m\)\(n=n_1+2*n_2+3*n_3...m*n_m\)+1哈夫曼树没有度为1的结点,也就是\(n_1=0\)完全二叉树常考总结最大岛屿问题(dfs模板)#include<iostream>#include<algorith......
  • Python_数据结构的应用heap
    数据结构栈-->stack队列-->queue树-->tree堆-->heap散列-->hash图-->graph图结构一般包括顶点和边邻接矩阵DAG,DirectedAcyclicGraph即「有向无环图」树树(Tree)是一种非线性的数据结构,由n个节点组成,其中每个节点都有零个或多个子节点。......
  • Redis数据结构3:REDIS_LISTNODE
    REDIS_LISTNODEREDIS_LISTNODE本质上与Java的LinkedList一致,NodeList即为链表,是基本的线性结构。C语言原生没有对链表的支持,Redis对链表进行了实现。listNodetypedefstructlistNode{structlistNode*prev;structlistNode*next;void*value;}listNode;l......
  • java-数据结构
    数据结构A:栈先进后出B:队列先进先出C:数组查询快,增删慢D:链表查询慢,增删快List的三个实现类(1)List的三个实现类特点A:ArrayList底层数据结构是数组,查询快,增删慢线程不安全,效率高B:Vector底层数据结构是数组,查询快,增删慢线程安全,效率低C:LinkedList底层数据结......
  • java-数据和集合 and 数据结构
    1:数组:基本类型的数组:int[]引用类型的数组:Student[]2:Collection集合(掌握)(1)集合的由来我们学习的是面向对象的语言,而面向对象的语言常见的操作就是操作对象。为了方便我们对多个对象进行操作,我们可以使用对象数组来进行。但是对象数组的长度是固定的,不适应变化的需求,所......