• 普通莫队小结

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

    • 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)个元素，再将每个块按顺序编号，然后排序（对于区间左端点来说，如果在同一个块内，就按右端点排序，否则按左端点排序）
    • 如果足够细心应该会注意到，对要询问的区间进行排序，那将会打乱原有的询问顺序
    • 换而言之，必须要先输入所有询问，再一次性输出所有对应的答案，也就是我们通常所说的离线操作
  • 相关阅读:
    数字验证学习笔记——SystemVerilog芯片验证12 ——句柄的使用&包的使用
    数学建模 —— MATLAB中的矩阵（下）
    python 从二进制文件中读取浮点数据
    【WinForm详细教程一】WinForm中的窗体、Label、TextBox及Button控件、RadioButton和CheckBox、ListBox
    MySql——索引
    new条件构造器的位置很重要
    学习c#的第十八天
    华为累计报考PMP超万人次，他们为什么要考呢？
    【云原生之k8s】k8s资源限制以及探针检查
    分享几个小技巧教你图片怎么加边框
  • 原文地址：https://blog.csdn.net/weixin_59624686/article/details/126200900