• 普通莫队小结

    • 无修改普通莫队大致的步骤如下：

    • 1.读入所有询问，离线解决
    • 2.按照左端点将询问分块
    • 3.以分块为第一关键字，右端点为第二关键字排序
    • 4.按照排序的顺序依次解决所有的询问
    • 可以使用奇偶性优化加快排序

    • 首先通过一个问题来引入

    • 问题：给你一个长度为n的数组，有m次查询，每次查询询问一个区间[L, R]内有多少个不同的数

    • 首先想想暴力怎么做

    • 开一个数组用来记数，然后扫一遍[L,R]，如果这个数是第一次出现，那么对答案贡献+1
    • 暴力出来的时间复杂度是O(n*m)，如果n、m较大，那暴力肯定是不行的。

    • 再想想进一步优化

    • 开两个指针 l 和 r，将之前的每次扫区间[L,R]改成移动指针l、r，使得指针与区间边界对齐
    • 在移动指针的时候，对应地去删除或添加对答案的贡献即可
    • 但问题来了，如果每次询问的区间[L,R]都需要移动很长的距离，就比如第一次询问[1,2]，第二次询问[n-1,n]，出现了一个指针反复横跳的情况
    • 这么一来时间复杂度依旧是O(n*m)
    • 优化了个寂寞

    • 这就需要我们给这些询问一个顺序，使得移动次数最小，这样我们可以利用上一次询问得到的信息来处理当前询问，大大加快速度

    • 回到刚才的第二种思路，我们可不可以在原来的基础上，对左区间进行排序以保证指针l不会移动到曾经被左指针扫过的地方，思想是好的，但是不能确保指针r的移动不重复，所以还是不行
    • 这个时候就需要进行分块
    • 核心是分块和排序：将长度为n的数组分为若干个块，每个块内有sqrt(n)个元素，再将每个块按顺序编号，然后排序（对于区间左端点来说，如果在同一个块内，就按右端点排序，否则按左端点排序）
    • 如果足够细心应该会注意到，对要询问的区间进行排序，那将会打乱原有的询问顺序
    • 换而言之，必须要先输入所有询问，再一次性输出所有对应的答案，也就是我们通常所说的离线操作
  • 相关阅读:
    【python复习笔记】
    力扣146｜LRU缓存淘汰算法
    webpack5 splitChunks 配置和用法
    VR全景展览——开启全新视界的虚拟展览体验
    【Sql】sql server还原数据库的时候，提示：因为数据库正在使用，所以无法获得对数据库的独占访问权。
    Node.js中的child_process模块的作用
    基于J2EE的弹幕视频网站设计
    Windows10/11 缩放与布局自定义
    解锁C语言结构体的力量（初阶）
    【操作系统】总结 (一) 机组部分知识
  • 原文地址：https://blog.csdn.net/weixin_59624686/article/details/126200900