题目描述
小B有一个序列,包含N个1~K之间的整数。他一共有M个询问,每个询问给定一个区间[L..R],求Sigma(c(i)^2)的值,其中i的值从1到K,其中c(i)表示数字i在[L..R]中的重复次数。小B请你帮助他回答询问。
输入格式
第一行,三个整数N、M、K。
第二行,N个整数,表示小B的序列。
接下来的M行,每行两个整数L、R。
输出格式
M行,每行一个整数,其中第i行的整数表示第i个询问的答案。
输入输出样例
输入 #1
6 4 3 1 3 2 1 1 3 1 4 2 6 3 5 5 6
输出 #1
6 9 5 2
说明/提示
对于全部的数据,1<=N、M、K<=50000
解题思路:莫队模板
1 #include <iostream> 2 #include <algorithm> 3 #include <cstdio> 4 #include <cstring> 5 #include <iomanip> 6 #include <set> 7 #include <map> 8 #include <vector> 9 #include <queue> 10 #include <cmath> 11 #define N 50005 12 #define ll long long 13 using namespace std; 14 15 int n,m,k,L,R; 16 int arr[N],cnt[N]; 17 ll res; 18 ll sum[N]; 19 20 struct Node{ 21 int l,r,b,ans; 22 bool operator<(const Node&X)const{ 23 if(ans!=X.ans) return ans<X.ans; 24 return r<X.r; 25 } 26 }A[N]; 27 28 void add(int ee){ 29 res+=2*cnt[arr[ee]]+1; 30 cnt[arr[ee]]++; 31 } 32 33 void del(int ee){ 34 cnt[arr[ee]]--; 35 res-=2*cnt[arr[ee]]+1; 36 } 37 38 39 int main(){ 40 scanf("%d%d%d",&n,&m,&k); 41 for(int i=1;i<=n;i++) scanf("%d",&arr[i]); 42 int big=(int)sqrt(n); 43 for(int i=1;i<=m;i++){ 44 scanf("%d%d",&A[i].l,&A[i].r); 45 A[i].b=i,A[i].ans=(A[i].l-1)/big+1; 46 } 47 L=1,R=0; 48 sort(A+1,A+1+m); 49 for(int i=1;i<=m;i++){ 50 while(L<A[i].l) del(L++); 51 while(L>A[i].l) add(--L); 52 while(R<A[i].r) add(++R); 53 while(R>A[i].r) del(R--); 54 sum[A[i].b]=res; 55 } 56 for(int i=1;i<=m;i++){ 57 printf("%lld ",sum[i]); 58 } 59 return 0; 60 }