3781: 小B的询问
Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 1039 Solved: 697
[Submit][Status][Discuss]
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
Sample Output
6
9
5
2
HINT
对于全部的数据，1<=N、M、K<=50000
Source
1 #include "bits/stdc++.h"
2 using namespace std;
3 typedef long long LL;
4 const int MAX=5e4+5;
5 int n,m;
6 LL a[MAX],b[MAX],pos[MAX],ans,an[MAX],bas;
7 struct Node{
8 int id;
9 int l,r;
10 bool operator < (const Node &tt) const {
11 if (pos[l]!=pos[tt.l])
12 return pos[l]<pos[tt.l];
13 return r<tt.r;
14 }
15 }que[MAX];
16 inline int read(){
17 int an=0,x=1;char c=getchar();
18 while (c<'0' || c>'9') {if (c=='-') x=-1;c=getchar();}
19 while (c>='0' && c<='9') {an=an*10+c-'0';c=getchar();}
20 return an*x;
21 }
22 void update(int x,int y){
23 ans-=b[a[x]]*b[a[x]];
24 b[a[x]]+=y;
25 ans+=b[a[x]]*b[a[x]];
26 }
27 int main(){
28 freopen ("ask.in","r",stdin);
29 freopen ("ask.out","w",stdout);
30 int i,j;
31 n=read();m=read();read();bas=(LL)sqrt(n*1.0);
32 memset(b,0,sizeof(b));
33 for (i=1;i<=n;i++) a[i]=read(),pos[i]=(i-1)/bas+1;
34 for (i=1;i<=m;i++){
35 que[i].id=i;
36 que[i].l=read();que[i].r=read();
37 }
38 sort(que+1,que+m+1);
39 int L=1,R=0;
40 for (i=1;i<=m;i++){
41 while (R<que[i].r){R++;update(R,1);}
42 while (L>que[i].l){L--;update(L,1);}
43 while (R>que[i].r){update(R,-1);R--;}
44 while (L<que[i].l){update(L,-1);L++;}
45 an[que[i].id]=ans;
46 }
47 for (i=1;i<=m;i++)
48 printf("%d\n",an[i]);
49 return 0;
50