本文共 1834 字，大约阅读时间需要 6 分钟。

小B有一个长为 $n$ 的整数序列 $a$ ，值域为 $[1,k]$ 。

输入格式

输出格式

输入输出样例

6 4 31 3 2 1 1 31 42 63 55 6

输出 #1

6952

说明/提示

思路：就是一个单纯的莫队题目。要注意的是，可能会爆 int 。

代码如下：

#include 
   
    using namespace std;const int maxn = 5e4 + 10;int a[maxn];				//记录数据,值域为[1,k] int pos[maxn];long long ans[maxn];		//结果可能超过int范围 long long res = 0;			//记录闭区间结果 int cnt[maxn]; 				//[1,k]值域的数ci出现几次 struct Q {
   	int l, r, i;			//[l,r]闭区间,i表示第几个询问 } q[maxn];//区间[l,r]的总贡献是其中每个数的出现次数的平方和 //区间扩展时,扩展的某格的数a[n]的出现次数+1,//我们需要减去该格的数原来出现次数的平方,加上该格数新的出现次数的平方 //一个小优化:(a+1)^2-a^2=2a+1 void Add(int n) {
   	res += (2 * cnt[a[n]] + 1);	++cnt[a[n]]; }//区间收缩时,收缩的某格的数a[n]的出现次数-1,//我们需要减去该格的数原来出现次数的平方,加上该格数新的出现次数的平方//一个小优化:(a-1)^2-a^2=-2a+1 void Sub(int n) {
   	res += (1 - 2 * cnt[a[n]]);	--cnt[a[n]];}int main() {
       int n, m, k;    scanf("%d%d%d", &n, &m, &k);    int size = sqrt(n);    for (int i = 1; i <= n; ++i) {
   		scanf("%d", &a[i]);		pos[i] = i / size;	}	for (int i = 0; i < m; ++i) {
   		scanf("%d%d", &q[i].l, &q[i].r);		q[i].i = i;	}	sort(q, q + m, [](const Q &a, const Q &b) {
   		return pos[a.l] == pos[b.l] ? a.r < b.r : pos[a.l] < pos[b.l];	});	//闭区间[l,r] 	int l = 1, r = 0;    for (int i = 0; i < m; ++i) {
       	while (q[i].l < l) Add(--l);    	while (q[i].r > r) Add(++r);    	while (q[i].l > l) Sub(l++);    	while (q[i].r < r) Sub(r--);    	ans[q[i].i] = res;    }    //打印结果	for (int i = 0; i < m; ++i) 		printf("%lld\n", ans[i]);     return 0;}
   

转载地址：https://memcpy0.blog.csdn.net/article/details/108210614 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！