C11l【模板】莫队算法 P2709 小B的询问

30分超时：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=5e4+10;
int n,m,k,a[N];
LL cnt[N],ans[N],sum;
struct node{ int l,r,id;}q[N];
bool cmp(const node &n1,const node &n2){return n1.l!=n2.l ? n1.l<n2.l : n1.r<n2.r;}
void add(int x)
{
    sum-=cnt[x]*cnt[x];
    cnt[x]++;
    sum+=cnt[x]*cnt[x];
}
void del(int x)
{
    sum-=cnt[x]*cnt[x];
    cnt[x]--;
    sum+=cnt[x]*cnt[x];
}
int main()
{
    scanf("%d%d%d", &n, &m, &k);
    for(int i=1;i<=n;i++)scanf("%d", &a[i]);
    for(int i=1;i<=m;i++)scanf("%d%d", &q[i].l, &q[i].r), q[i].id=i;
    sort(q+1,q+1+m,cmp);
    sum=0;memset(cnt,0,sizeof(cnt));memset(ans,0,sizeof(ans));
    for(int i=1,l=1,r=0;i<=m;i++)
    {
        while(l>q[i].l) add(a[--l]);//注意：先扩再收
        while(r<q[i].r) add(a[++r]);
        while(l<q[i].l) del(a[l++]);
        while(r>q[i].r) del(a[r--]);
        ans[q[i].id]=sum;
    }
    for(int i=1;i<=m;i++)printf("%lld\n",ans[i]); 
    return 0;
}