[CF 86D] Powerful array · 莫隊算法

莫隊算法闆子題，再打一遍增強記憶。

1.記得處理詢問中l==r的情況。

2.注意long long

今天才知道原來CF是架在Windows上的。。。

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <cmath>
#include <cstring>
using namespace std;
#define ll long long
#define sqr(x) ((ll)(x)*(ll)(x))

const int N=200005;

int n,m,a[N],cnt[N*5],l,r;
int belong[N],k,tot;
struct arr{
	int	l,r,num;
}q[N];
ll Ans,ans[N];

bool cmp(const arr A,const arr B){
	if (belong[A.l]==belong[B.l]) return A.r<B.r;
	return A.l<B.l;
}

int get(){
	int p=0;char x=getchar();
	while (x<'0' || x>'9') x=getchar();
	while (x>='0' && x<='9') p=p*10+x-'0',x=getchar();
	return p;
}

void update(long long p,long long t){
	p=a[p];
	Ans-=(ll)sqr(cnt[p])*p;
	cnt[p]+=t;
	Ans+=(ll)sqr(cnt[p])*p;
}

int main(){
	n=get();m=get();
	k=sqrt(m);
	for (int i=1;i<=n;i++) a[i]=get();
	for (int i=1;i<=m;i++)
		q[i].l=get(),q[i].r=get(),q[i].num=i,belong[i]=(i-1)/k+1;
	sort(q+1,q+m+1,cmp);
	l=1;r=0;
	for (int i=1;i<=m;i++){
		if (q[i].l==q[i].r) {
			ans[q[i].num]=a[q[i].l];
			continue;
		}
		for (;l<q[i].l;l++) update(l,-1);
		for (;l>q[i].l;l--) update(l-1,1);
		for (;r<q[i].r;r++) update(r+1,1);
		for (;r>q[i].r;r--) update(r,-1);
		ans[q[i].num]=Ans;
	}
	for (int i=1;i<=m;i++) printf("%I64d\n",ans[i]);
	return 0;
}