• 普通莫队小结

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

    • 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)个元素，再将每个块按顺序编号，然后排序（对于区间左端点来说，如果在同一个块内，就按右端点排序，否则按左端点排序）
    • 如果足够细心应该会注意到，对要询问的区间进行排序，那将会打乱原有的询问顺序
    • 换而言之，必须要先输入所有询问，再一次性输出所有对应的答案，也就是我们通常所说的离线操作
  • 相关阅读:
    vue多种实现动画效果分享【推荐学习】
    【前端开发】可拖拽浮窗组件
    超硬核解析！Apache Hudi灵活的Payload机制
    【高危】GitLab CE/EE 16.0.0存在路径遍历漏洞（存在POC）
    使用apriltag_ros检测相机姿态
    正点原子嵌入式linux驱动开发——STM32MP1启动详解
    Unity使用新输入系统InputSystem制作飞机大战Demo（实现能量系统）
    数据结构之数组练习
    机械臂模型更换成自己的urdf模块
    C#实践炸飞机socket通信
  • 原文地址：https://blog.csdn.net/weixin_59624686/article/details/126200900