3781: 小B的询问
Description
小B有一个序列，包含N个1~K之间的整数。他一共有M个询问，每个询问给定一个区间[L..R]，求Sigma(c(i)^2)的值,其中i的值从1到K，其中c(i)表示数字i在[L..R]中的重复次数。小B请你帮助他回答询问。
Input
第一行，三个整数N、M、K。
第二行，N个整数，表示小B的序列。
接下来的M行，每行两个整数L、R。
Output
M行，每行一个整数，其中第i行的整数表示第i个询问的答案。
Sample Input
6 4 3
1 3 2 1 1 3
1 4
2 6
3 5
5 6
1 3 2 1 1 3
1 4
2 6
3 5
5 6
Sample Output
6
9
5
2
9
5
2
HINT
对于全部的数据，1<=N、M、K<=50000
莫队算法
#include<cmath>
#include<cstdio>
#include<algorithm>
using namespace std;
int N,M,K,P;
int A[50010];
int cnt[50010];
struct Mo{
int k;
int l,r,BL;
int ans;
Mo(){}
Mo(int x,int a,int b){
k=x; l=a; r=b; BL=(a-1)/K+1;
}
}Que[50010];
bool cmp(const Mo &a,const Mo &b){
return a.BL<b.BL || a.BL==b.BL&&a.r<b.r;
}
bool cmp_k(const Mo &a,const Mo &b){
return a.k<b.k;
}
int main(){
scanf("%d%d%d",&N,&M,&P);
for (int i=1;i<=N;++i)
scanf("%d",&A[i]);
K=sqrt(N);
for (int i=1;i<=M;++i){
int x,y;
scanf("%d%d",&x,&y);
Que[i]=Mo(i,x,y);
}
sort(Que+1,Que+M+1,cmp);
int l=1,r=1,Ans=1;
cnt[A[1]]=1;
for (int i=1;i<=M;++i){
for (;r<Que[i].r;)
Ans=Ans+2*(cnt[A[++r]]++)+1;
for (;r>Que[i].r;)
Ans=Ans-2*(cnt[A[r--]]--)+1;
for (;l<Que[i].l;)
Ans=Ans-2*(cnt[A[l++]]--)+1;
for (;l>Que[i].l;)
Ans=Ans+2*(cnt[A[--l]]++)+1;
Que[i].ans=Ans;
}
sort(Que+1,Que+M+1,cmp_k);
for (int i=1;i<=M;++i)
printf("%d\n",Que[i].ans);
}
评论 (0)
