P2709 小B的询问

· · 题解

P2709 小B的询问

题目翻译：

给定一个长度为 n 的序列 a，m 次询问，每次给定一个区间 [l,r] 求这个区间内出现的每一种数字的个数的平方和

思路：

发现是区间的查询次数，考虑使用莫队来离线处理答案，主要部分没有太大区别，主要是在更新删减点的时候做改变。

我们发现求的是次数的平方和，若增加一个点，那出现次数增加一，及 x \rightarrow x+1 那答案变化为 x^2 \rightarrow (x+1)^2 及 x^2 \rightarrow x^2+2x+1 那最终答案就变化了 2x+1 ，那只需要将答案增加 2x+1 同理删点就减去 2x-1 

int sum;
void add(int i){
    sum+=2*cnt[i]+1;;
    cnt[i]++;
} 
void del(int i){
    sum-=2*cnt[i]-1;
    cnt[i]--;   
}

完整代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=50010;
int a[N],cnt[N];
struct query{
    int l,r,id,k;
}q[N];
int ans[N];
bool cmp(query x,query y){
    if(x.k!=y.k){
        return x.k<y.k;
    }
    else if(x.k&1){
        return x.r<y.r;
    }
    else{
        return x.r>y.r; 
    }
}
int sum;
void add(int i){
    sum+=2*cnt[i]+1;;
    cnt[i]++;
} 
void del(int i){
    sum-=2*cnt[i]-1;
    cnt[i]--;   
}
signed main(){
    int n,m,num;
    scanf("%lld%lld%lld",&n,&m,&num);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    int len=sqrt(n);
    for(int i=1;i<=m;i++){
        int l,r;
        scanf("%lld%lld",&l,&r);
        q[i]={l,r,i,l/len};
    }

    sort(q+1,q+m+1,cmp);
    int l=1,r=0;
    for(int i=1;i<=m;i++){
        int ll=q[i].l;
        int rr=q[i].r;
        while(l>ll)add(a[--l]);
        while(r<rr)add(a[++r]);
        while(l<ll)del(a[l++]);
        while(r>rr)del(a[r--]);
        ans[q[i].id]=sum;
    }
    for(int i=1;i<=m;i++){
        printf("%lld\n",ans[i]);
    }
}

莫队讲解