洛谷 P2709：[模板] 莫队 / 小 B 的询问 ← 莫队算法

【题目来源】
https://www.luogu.com.cn/problem/P2709

【题目描述】
小 B 有一个长为 n 的整数序列 a，值域为 [1,k]。
他一共有 m 个询问，每个询问给定一个区间 [l,r]，求：
其中 ci 表示数字 i 在 [l,r] 中的出现次数。
小 B 请你帮助他回答询问。

【输入格式】
第一行三个整数 n，m，k。
第二行 n 个整数，表示小 B 的序列。
接下来的 m 行，每行两个整数 l，r。​​​​​​​

【输出格式】
输出 m 行，每行一个整数，对应一个询问的答案。​​​​​​​

【输入样例】
6 4 3
1 3 2 1 1 3
1 4
2 6
3 5
5 6​​​​​​​

【输出样例】
6
9
5
2

【数据范围】
对于 100% 的数据，1≤n,m,k≤10^5。

【算法分析】
● 基础莫队算法（Mo's Algorithm）​ 是一种用于解决离线区间查询问题的算法，由莫涛在 2010 年提出。莫队算法是‌基于分块思想‌构建的离线区间查询优化算法，分块为其提供‌排序依据与复杂度保障‌，两者关系可概括为"‌莫队=离线+暴力转移+分块排序‌"。‌

● 莫队算法是一种用于解决离线区间查询问题的算法，其核心思想是通过分块排序来优化指针移动顺序，从而降低总时间复杂度。奇偶性排序是莫队算法中的一个重要优化技巧，具体实现如下：
（1）首先，将长度为 n 的序列分成 sqrt(n) 个块；
（2）然后，将所有询问按左端点 L 所在的块编号为第一关键字排序。当左端点在同一块内时，采用奇偶性排序优化右端点 R 的顺序：若左端点位于奇数块，则右端点 R 从小到大排序；若左端点位于偶数块，则右端点 R 从大到小排序。
这样可以减少右指针在块间切换时的回跳次数，进一步提升算法效率。​​​​​​​

【算法代码】

#include <bits/stdc++.h> using namespace std; typedef long long LL; const int N=1e5+5; LL a[N],cnt[N],ans[N]; LL cur; int block,n,m,k; struct Node { int le,ri,idx; } q[N]; bool cmp(Node a,Node b) { if(a.le/block!=b.le/block) { return a.le<b.le; } return a.ri<b.ri; } void add(int x) { int val=a[x]; cur+=2*cnt[val]+1; cnt[val]++; } void del(int x) { int val=a[x]; cnt[val]--; cur-=2*cnt[val]+1; } int main() { ios::sync_with_stdio(false); cin.tie(0); cin>>n>>m>>k; for(int i=1; i<=n; i++) cin>>a[i]; block=sqrt(n); for(int i=0; i<m; i++) { cin>>q[i].le>>q[i].ri; q[i].idx=i; } sort(q,q+m,cmp); int le=1,ri=0; for(int i=0; i<m; i++) { while(le>q[i].le) add(--le); while(le<q[i].le) del(le++); while(ri<q[i].ri) add(++ri); while(ri>q[i].ri) del(ri--); ans[q[i].idx]=cur; } for(int i=0; i<m; i++) { cout<<ans[i]<<"\n"; } return 0; } /* in: 6 4 3 1 3 2 1 1 3 1 4 2 6 3 5 5 6 out: 6 9 5 2 */

【参考文献】
https://blog.csdn.net/hnjzsyjyj/article/details/138976338