BZOJ3781:小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

Sample Output

6
9
5
2

HINT

对于全部的数据，1<=N、M、K<=50000

Solution

莫队水题

Code

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<algorithm>

 #include<cmath>

 #define N (50000+100)

 using namespace std;

 struct node

 {

     int l,r,id,ans,ord;

 }Ask[N];

 int a[N],n,m,k,cnt[N],Sigma,l=,r=;

 bool cmp1 (node a,node b){return a.id==b.id?a.r<b.r:a.id<b.id;}

 bool cmp2 (node a,node b){return a.ord<b.ord;}

 void Ins(int x)

 {

     Sigma-=cnt[x]*cnt[x];

     cnt[x]++;

     Sigma+=cnt[x]*cnt[x];

 }

 void Del(int x)

 {

     Sigma-=cnt[x]*cnt[x];

     cnt[x]--;

     Sigma+=cnt[x]*cnt[x];

 }

 void MoQueue(int x)

 {

     int L=Ask[x].l,R=Ask[x].r;

     while (l<L) Del(a[l++]);

     while (l>L) Ins(a[--l]);

     while (r<R) Ins(a[++r]);

     while (r>R) Del(a[r--]);

     Ask[x].ans=Sigma;

 }

 int main()

 {

     scanf("%d%d%d",&n,&m,&k);

     int len=pow(n,2.0/3.0);

     for (int i=;i<=n;++i)

         scanf("%d",&a[i]);

     for (int i=;i<=m;++i)

     {

         scanf("%d%d",&Ask[i].l,&Ask[i].r);

         Ask[i].id=Ask[i].l/len;

         Ask[i].ord=i;

     }

     sort(Ask+,Ask+m+,cmp1);

     for (int i=;i<=m;++i)

         MoQueue(i);

     sort(Ask+,Ask+m+,cmp2);

     for (int i=;i<=m;++i)

         printf("%d\n",Ask[i].ans);

 }

巴特西