区间内不同元素个数查询（Mo's Algorithm） 题目描述 给定一个长度为n的数组和多个查询，每个查询要求回答某个区间[ L, R]内有多少个不同的元素。例如数组[ 1,2,3,2,2,1,3]，查询[ 2,5 ]（下标从1开始）的结果是2（元素2和3）。 解题过程 1. 问题分析 直接方法：对每个查询遍历区间统计不同元素，时间复杂度O(n* q)（q为查询次数） 核心矛盾：多个查询间存在区间重叠，直接法没有利用这个特性 关键思路：通过合理安排查询顺序，利用前一个查询的结果来加速后一个查询 2. 算法核心思想 将查询按特定规则分组排序 使用双指针维护当前区间 通过指针的移动来更新不同元素的计数 利用前一次查询的结果减少重复计算 3. 排序策略详解 将数组分成√n个块（块大小=√n） 排序规则：先按L所在的块号排序，块号相同则按R排序 奇数块内R升序，偶数块内R降序（优化技巧） 4. 数据结构设计 count[ x ]：记录元素x在当前区间出现的次数 distinct_ count：记录当前区间不同元素个数 当count[ x]从0→1时，distinct_ count加1 当count[ x]从1→0时，distinct_ count减1 5. 指针移动操作 左指针移动： 左指针右移（L++）：移除元素arr[ L]，count[ arr[ L] ]-- 如果count[ arr[ L]]变为0，distinct_ count-- 左指针左移（L--）：添加元素arr[ L-1]，count[ arr[ L-1] ]++ 如果count[ arr[ L-1]]从0→1，distinct_ count++ 右指针移动： 右指针右移（R++）：添加元素arr[ R+1]，count[ arr[ R+1] ]++ 如果count[ arr[ R+1]]从0→1，distinct_ count++ 右指针左移（R--）：移除元素arr[ R]，count[ arr[ R] ]-- 如果count[ arr[ R]]变为0，distinct_ count-- 6. 完整算法步骤 计算块大小block_ size = √n 将查询按(L/block_ size, R)排序 初始化L=1, R=0, distinct_ count=0 对每个查询[ Lq, Rq ]： while R < Rq: R++并添加arr[ R ] while R > Rq: 移除arr[ R ]并R-- while L < Lq: 移除arr[ L ]并L++ while L > Lq: L--并添加arr[ L ] 记录当前distinct_ count作为查询结果 7. 复杂度分析 左指针移动：每个查询最多移动O(√n)次，总共O(q√n) 右指针移动：在每个块内单调移动，总共O(n√n) 总时间复杂度：O((n+q)√n) 空间复杂度：O(n)用于存储count数组 8. 优化技巧 奇偶排序：减少右指针的来回移动 块大小调整：实际可用n/√q作为块大小 离散化：如果元素值很大，先映射到小范围 这种算法特别适合处理多个区间查询问题，通过巧妙的排序将时间复杂度从O(nq)优化到O((n+q)√n)。