[bzoj] 3781 小B的询问 || 莫队

原题

求[l,r]区间内(a[i]^2)的和

---

莫队板子题。
//另：因为(a^2)与((a+1)^2)是不能直接转换的，所以要先+后-（先-后+）

#include<cstdio>
#include<algorithm>
#include<cmath>
#define N 50010
typedef long long ll;
using namespace std;
struct hhh
{
    int x,y,l,id;
    bool operator < (const hhh &b) const
	{
	    if (b.l==l) return y<b.y;
	    return l<b.l;
	}
}q[N];
ll n,m,s,k,l,r,a[N],ans[N],cur,cnt[N];

ll read()
{
    ll ans=0,fu=1;
    char j=getchar();
    for (;j<'0' || j>'9';j=getchar()) if (j=='-') fu=-1;
    for (;j>='0' && j<='9';j=getchar()) ans*=10,ans+=j-'0';
    return ans*fu;
}

ll sqr(ll x)
{
    return x*x;
}

int main()
{
    n=read();s=sqrt(n);cnt[0]=1;
    m=read();
    k=read();
    for (int i=1;i<=n;i++) a[i]=read();
    for (int i=1;i<=m;i++)
    {
	q[i].x=read();
	q[i].y=read();
	q[i].id=i;
	q[i].l=(q[i].x-1)/s+1;
    }
    sort(q+1,q+m+1);
    for (int i=1;i<=m;i++)
    {
	while (l<q[i].x) cur-=sqr(cnt[a[l]]--),cur+=sqr(cnt[a[l++]]);
	while (l>q[i].x) cur-=sqr(cnt[a[--l]]++),cur+=sqr(cnt[a[l]]);
	while (r<q[i].y) cur-=sqr(cnt[a[++r]]++),cur+=sqr(cnt[a[r]]);
	while (r>q[i].y) cur-=sqr(cnt[a[r]]--),cur+=sqr(cnt[a[r--]]);
	ans[q[i].id]=cur;
    }
    for (int i=1;i<=m;i++)
	printf("%lld
",ans[i]+1);
    return 0;
}