入门oj 6492: 小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。
1<=N、M、K<=50000

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 //在区间[1..4]]之间，1出现了2次，2和3分别出现1次，于是结果=4+1+1=6

9

5

2

HINT

1莫队算法

2因为是求出Sigma(c(i)^2)的值，所以在模板上要改进一下

3可知当c(i)++,总和加上c(i+1)^-c(i)^=c(i)*2+1，就有了代码中的ans+=num[x]*2+1;(如果在最后再枚举一遍会超时，所以要在线统计，c(i)--的情况读者可以先自行推导再看代码）

#include<bits/stdc++.h>

using namespace std;

long long n,m,cnt[200000],ans,k,num[1000001],l,r,anss[200001];

struct data {

    long long ll,rr,num;

}a[200001];

bool cmp(data c,data d) {

    long long bol=sqrt(n);

    if(c.ll/bol==d.ll/bol)

        return c.rr<d.rr;

    else

        return c.ll/bol<d.ll/bol;

}//莫队排序

void add(long long xx){

    long long x=cnt[xx];

    ans+=num[x]*2+1;

    num[x]++;

}

void del(long long xx){

    long long x=cnt[xx];

    if(num[x]-1>=0)

    ans=ans-num[x]*2+1,

    num[x]--;

}

void dowork(long long x){

    while(l>a[x].ll) add(--l);

    while(r<a[x].rr) add(++r);

    while(l<a[x].ll) del(l++);

    while(r>a[x].rr) del(r--);

anss[a[x].num]=ans;

}//莫队板子

int main(){

    cin>>n>>m>>k;

    for(long long i=1;i<=n;i++){

        scanf("%lld",&cnt[i]);

    }

    for(long long i=1;i<=m;i++){

        scanf("%lld%lld",&a[i].ll,&a[i].rr);

        a[i].num=i;

    }

    sort(a+1,a+m+1,cmp);

    for(long long i=1;i<=m;i++){

        dowork(i);

    }

    for(long long i=1;i<=m;i++)

    printf("%lld\n",anss[i]);

}

巴特西