洛谷 P2709 小B的询问（莫队）

题目链接：https://www.luogu.com.cn/problem/P2709

这道题是模板莫队，然后$i$在$[l,r]$区间内的个数就是$vis[ ]$数组

$add()$和$del()$的话就是先减去原来位置数的个数的平方，然后再加上现在位置数的个数的平方。

AC代码：

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cmath>
 4 #include<algorithm>
 5 
 6 using namespace std;
 7 const int N=50005;
 8 
 9 int a[N],vis[N],ans,tot[N];
10 int block;
11 
12 struct node{
13     int l,r;
14     int id;
15 }q[N];
16 
17 bool cmp(node aa,node bb){
18     if(aa.l/block==bb.l/block) return aa.r<bb.r;
19     return aa.l/block<bb.l/block;
20 }
21 
22 void add(int pos){
23     ans-=vis[a[pos]]*vis[a[pos]];
24     vis[a[pos]]++;
25     ans+=vis[a[pos]]*vis[a[pos]];
26 }
27 
28 void del(int pos){
29     ans-=vis[a[pos]]*vis[a[pos]];
30     vis[a[pos]]--;
31     ans+=vis[a[pos]]*vis[a[pos]];
32 }
33 
34 int main(){
35     int n,m,k;
36     scanf("%d%d%d",&n,&m,&k);
37     block=sqrt(n);
38     for(int i=1;i<=n;i++) scanf("%d",&a[i]);
39     for(int i=1;i<=m;i++){
40         scanf("%d%d",&q[i].l,&q[i].r);
41         q[i].id=i;
42     }
43     sort(q+1,q+m+1,cmp);
44     int L=1,R=0;
45     for(int i=1;i<=m;i++){
46         while(L>q[i].l){
47             L--;
48             add(L);
49         }
50         while(L<q[i].l){
51             del(L);
52             L++;
53         }
54         while(R<q[i].r){
55             R++;
56             add(R);
57         }
58         while(R>q[i].r){
59             del(R);
60             R--;
61         }
62         tot[q[i].id]=ans;
63     }
64     for(int i=1;i<=m;i++) printf("%d
",tot[i]);
65     return 0;
66 }

AC代码