小B的询问(题解)(莫队)

题目

code

#include<bits/stdc++.h>

#define lst long long

#define ldb double

#define N 50050

using namespace std;

const int Inf=1e9;

int read()

{

    int s=0,m=0;char ch=getchar();

    while(ch<'0'||ch>'9'){if(ch=='-')m=1;ch=getchar();}

    while(ch>='0'&&ch<='9')s=(s<<3)+(s<<1)+(ch^48),ch=getchar();

    return m?-s:s;

}

int n,m,K,unit;lst Ans;

int v[N],bl[N];lst sum[N];

struct QUES{int le,ri,id;lst ans;}ljl[N];

bool cmp_ut(QUES &a,QUES &b){return bl[a.le]==bl[b.le]?a.ri<b.ri:a.le<b.le;}

bool cmp_id(QUES &a,QUES &b){return a.id<b.id;}

void Update(int now,int add)

{

    Ans-=sum[v[now]]*sum[v[now]];

    sum[v[now]]+=add;

    Ans+=sum[v[now]]*sum[v[now]];return;

}

int main()

{

    n=read(),m=read(),K=read();unit=sqrt(n);

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

        v[i]=read(),bl[i]=i/unit+1;

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

        ljl[i]=(QUES){read(),read(),i};

    sort(ljl+1,ljl+m+1,cmp_ut);

    int ll=1,rr=0;

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

    {

        while(ll<ljl[i].le)Update(ll,-1) ,ll++;

        while(ll>ljl[i].le)Update(ll-1,1),ll--;

        while(rr<ljl[i].ri)Update(rr+1,1),rr++;

        while(rr>ljl[i].ri)Update(rr,-1) ,rr--;

        ljl[i].ans=Ans;

    }

    sort(ljl+1,ljl+m+1,cmp_id);

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

        printf("%lld\n",ljl[i].ans);

    return 0;

}
巴特西

小B的询问(题解)(莫队)

小B的询问(题解)(莫队)

题目

code

最新文章

热门文章
