【BZOJ3781】小B的询问

  裸的莫队。

#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int maxn=50010;

struct Query
{
	int l,r,block,id;
	bool operator< (const Query &b) const {return block<b.block || block==b.block && r<b.r;}
}Q[maxn];

int a[maxn];
int cnt[maxn];
int n,m,k,V;
LL ans[maxn];

int main()
{
	scanf("%d%d%d",&n,&m,&k);
	V=sqrt(n)+1;
	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].block=Q[i].l/V,Q[i].id=i;
	sort(Q+1,Q+1+m);
	LL res=0;
	for (int i=1,l=1,r=0;i<=m;i++)
	{
		while (l<Q[i].l) cnt[a[l]]--,res-=2ll*cnt[a[l]]+1,l++;
		while (l>Q[i].l) l--,res+=2ll*cnt[a[l]]+1,cnt[a[l]]++;
		while (r<Q[i].r) r++,res+=2ll*cnt[a[r]]+1,cnt[a[r]]++;
		while (r>Q[i].r) cnt[a[r]]--,res-=2ll*cnt[a[r]]+1,r--;
		ans[Q[i].id]=res;
	}
	for (int i=1;i<=m;i++) printf("%lld\n",ans[i]);
	return 0;
}