洛谷 P2709：[模板] 莫队 / 小 B 的询问 ← 莫队算法-拓冰建站

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

【题目描述】
小 B 有一个长为 n 的整数序列 a，值域为 [1,k]。
他一共有 m 个询问，每个询问给定一个区间 [l,r]，求： $\sum_{i=1}^kc_i^2$
其中 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 6out:
6
9
5
2
*/