首页 > 其他分享 >数据结构

数据结构

时间:2024-01-27 20:34:26浏览次数:25  
标签:回滚 询问 sqrt 端点 区间 数据结构 莫队

早就学过了,学了就只学了

不能再颓下去了

莫队

一般用来解决静态区间询问问题,如果 \([l,r]\) 的答案能扩展到 \([l\pm\mathtt{1},r\pm\mathtt{1}]\),那么我们就能使用莫队在 \(O(n\sqrt{n})\) 复杂度内完成所有询问的答案,这里设 \(n,m\) 同阶。这个根号怪死了,还有我删除线咋还没了/fn

思想很简单,将询问离线后排序,暴力从上一个区间的答案转移到下一个区间答案(一步一步移动即可)。

排序一般按 \(l\) 所在块的编号为第一关键字,\(r\) 为第二关键字,一般也会加玄学的奇偶性排序。还有一般的块长都设 \(\dfrac{n}{\sqrt{m}}\),不同的莫队理论最优的块长也不同。

一般核心在于这里:

ll l=1,r=0,res=0; //res是答案
for(int i=1;i<=m;++i){
	阿巴阿巴;
	while(l>q[i].l) add(--l);
	while(l<q[i].l) del(l++);
	while(r>q[i].r) del(r--);
	while(r<q[i].r) add(++r);
	ans[q[i].id]=res;
}

做几道题就懂了。

回滚莫队

因为要做题就先写这个了。

OI-wiki上的描述:有些题目在区间转移时,可能会出现增加或者删除无法实现的问题。在只有增加不可实现或者只有删除不可实现的时候,就可以使用回滚莫队在 \(n\sqrt{m}\) 的时间内解决问题。回滚莫队的核心思想就是:既然只能实现一个操作,那么就只使用一个操作,剩下的交给回滚解决。回滚莫队分为只增和只减,具体看题目。

例题:歴史の研究

我们发现增加一个元素很好解决,它若要对答案产生影响就一定是新的最大值,但删除元素时我们不好判断剩下区间中的最大重要值是啥,这个时候就是只增加莫队了。

操作过程如下(不想写直接粘了):

  • 对原序列进行分块,对询问按以左端点所属块编号升序为第一关键字,右端点升序为第二关键字的方式排序。

  • 按顺序处理询问:

    • 如果询问左端点所属块 \(B\) 和上一个询问左端点所属块的不同,那么将莫队区间的左端点初始化为 \(B\) 的右端点加 \(1\), 将莫队区间的右端点初始化为 \(B\) 的右端点;

    • 如果询问的左右端点所属的块相同,那么直接扫描区间回答询问;

    • 如果询问的左右端点所属的块不同:

      • 如果询问的右端点大于莫队区间的右端点,那么不断扩展右端点直至莫队区间的右端点等于询问的右端点;

      • 不断扩展莫队区间的左端点直至莫队区间的左端点等于询问的左端点;

      • 回答询问;

      • 撤销莫队区间左端点的改动,使莫队区间的左端点回滚到 \(B\) 的右端点加 \(\mathtt{1}\)。

复杂度不想证,块长最优取 \(\dfrac{n}{\sqrt{m}}\),当然有时候更玄学的更好,但稳妥起见还是用这个,正式赛应该不怎么卡常吧。

还是把代码写了才能理解,多做几道题就上手了。

标签:回滚,询问,sqrt,端点,区间,数据结构,莫队
From: https://www.cnblogs.com/heshuwan/p/17991881

相关文章

  • 数据结构——顺序队列(循环)
    采用顺序表的方式实现循环队列。其中关键在于如何判断队列已满。通常情况下,当对头和队尾指向同一个节点时,可以判断为队空。但是,倘若队尾不断增加,最后队尾也会指向对头,此时队满和队空的判断条件一致。以下有三种对于对于队满判断的方法。1、舍弃顺序表中的一个元素,也就是说,当队尾......
  • 数据结构总结
    P4198楼房重建非常好题目,首先你显然能够得到一个楼房看得见的条件:当斜率严格大于之前的所有斜率时,这栋楼房可以被看见。接着我们考虑线段树\(sum_i\)维护\([l,r]\)从\(l\)出发可以看到的楼房数。我们发现重点在于push_up函数的实现,设左区间为\(ls\),右区间为\(rs\)。......
  • 29-数据结构介绍
          ......
  • 做题记录(数据结构+整体二分专题)
    情报传递对于每一个操作打上时间戳,对于\(T\)时刻的询问,即为询问路径上比\(T-c\)的值小的数有几个。直接树剖上维护权值树状数组即可。宝石给定一棵树,\(n\)个顶点,每个点有一个宝石,类型为\(W_i\),约定\(W_i\lem\)。你有一个收集器,可以收集至多\(c\)个宝石,并且收集......
  • 【数据结构】72变的双端队列
    双端队列前言大家好,很高兴又和大家见面啦!!!在前面的篇章中,咱们详细介绍了队列这种新的数据结构,现在我们简单的回顾一下队列的三要素——数据的逻辑结构、数据的存储结构以及数据的运算。数据的逻辑结构队列的数据元素在逻辑上是呈现线性结构,也就是说队列也是一种线性表,只不过是一种......
  • 数据结构与算法 pdf下载
    《数据结构与算法》涉及计算机中数据的组织、重组、移动、使用和提取等操作方法,及相关的数学分析。《数据结构与算法》所选的主题基于以下几个朴素的原则。第一,本书只讲解实用的技术,而忽略一些理论上非常虽然出色、但不太实用的算法。第二,本书既包含经典的方法,也包括最近发现的......
  • 【C语言进阶篇】看完这篇结构体文章,我向数据结构又进了一大步!(结构体进阶详解)
    (文章目录)......
  • 数据结构--堆
    前言​ 在实际很多的应用场景中,我们对数据进行处理的时候,比如插入数据和删除数据时,我们常常需要快速的知道数据中最大值和最小值。而处理这种问题的方法之一,就是使用一个已经排序好的数据集合。通过这种方式,数据的最大值或最小值总是在数据集合的头部或者尾部(这取决于使用时升序......
  • 数据结构
    哈希表也称为散列表,用于实现键值对的存储和查找。hash值的计算通常通过与运算hash&(m-1)方式实现,其桶的数量必须为2的次幂数(也可以通过取模hash%m计算hash值)。哈希函数将键映射到索引的位置,时间复杂度为O(1)(最坏O(n)),常见的有开放地址法和链表法两种:开放地址法:当发生哈希冲突时,......
  • 数据结构学习中测试代码
    线性表顺序表的一些基本性质//#defineprint(x) std::cout<<x<<std::endl//#defineget(x) std::cin>>x#include<iostream>#include<fstream>usingnamespacestd;#defineInitsize100#typedefstruct{ int*data; intMaxsize,leng......