• 普通莫队小结

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

    • 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)个元素，再将每个块按顺序编号，然后排序（对于区间左端点来说，如果在同一个块内，就按右端点排序，否则按左端点排序）
    • 如果足够细心应该会注意到，对要询问的区间进行排序，那将会打乱原有的询问顺序
    • 换而言之，必须要先输入所有询问，再一次性输出所有对应的答案，也就是我们通常所说的离线操作
  • 相关阅读:
    java毕业设计—— 基于java+javaEE+jsp的项目管理系统设计与实现（毕业论文+程序源码）——项目管理系统
    今年最后一次PMP考试！想升职加薪抓紧！
    基于RASC的keil电子时钟制作(瑞萨RA)(7)----配置RTC时钟及显示时间
    【总结】坐标变换和过渡矩阵（易忘记）
    Spring Boot集成protobuf快速入门Demo
    十五、项目构建与部署
    七、【Vue-Router】router-link标签的replace属性
    Mysql存储-EAV模式
    MySQL数据库基础操作
    Java筑基32-IO流02-节点流&处理流
  • 原文地址：https://blog.csdn.net/weixin_59624686/article/details/126200900