C++14(g++5.4) 解法, 执行用时: 516ms, 内存消耗: 6372K, 提交时间: 2019-09-15 17:21:29

#include <bits/stdc++.h>
using namespace std;
const int maxn=500000+20;
#define int long long
struct note{
	int l,r,id;
}q[maxn];
int l,r,s,sum,n,m,k;
int ans[maxn],pos[maxn],b[maxn]; 

inline bool cmp(note x,note y){
	if(x.r/s==y.r/s){
		return x.l<y.l;
	}else{
		return x.r<y.r;
	}
}
void add(int x){
	ans[b[x]]++;
	sum+=(ans[b[x]]*2-1)*b[x];
}
void del(int x){
	sum-=(ans[b[x]]*2-1)*b[x];
	ans[b[x]]--;
}
signed main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>b[i];
	}
	s=sqrt(n);
	for(int i=1;i<=m;i++){
		cin>>q[i].l>>q[i].r;
		q[i].id=i;
	}
	sort(q+1,q+m+1,cmp);
	int l=1,r=0;
	for(int i=1;i<=m;i++){
		int ql=q[i].l,qr=q[i].r;
		while(l<ql)del(l),l++;
		while(l>ql)l--,add(l);
		while(r<qr)r++,add(r);
		while(r>qr)del(r),r--;
		pos[q[i].id]=sum;
	}
	for(int i=1;i<=m;i++){
		cout<<pos[i]<<endl;
	}
}

C++(g++ 7.5.0) 解法, 执行用时: 241ms, 内存消耗: 4980K, 提交时间: 2022-11-09 21:17:50

#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;

struct node
{
	int l,r,id;
}Q[100005];
long long t=0,l=1,r=0,block,ans[100005],V[100005]={0},a[100005];
bool cmp(node a,node b)
{
	if(a.l/block==b.l/block)return a.r<b.r;
	return a.l/block<b.l/block;
}
void add(int x,int p)
{
	t+=p*a[x]*(2*V[a[x]]+p);
	V[a[x]]+=p;
}
int main()
{
	int i,n,m;
	scanf("%d%d",&n,&m),block=sqrt(n);
	for(i=1;i<=n;i++)scanf("%lld",&a[i]);
	for(i=1;i<=m;i++)scanf("%lld%lld",&Q[i].l,&Q[i].r),Q[i].id=i;
	sort(Q+1,Q+1+m,cmp);
	for(i=1;i<=m;i++)
	{
		while(l<Q[i].l)add(l++,-1);
		while(l>Q[i].l)add(--l,1);
		while(r<Q[i].r)add(++r,1);
		while(r>Q[i].r)add(r--,-1);
		ans[Q[i].id]=t;
	}
	for(i=1;i<=m;i++)printf("%lld\n",ans[i]);
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 276ms, 内存消耗: 6704K, 提交时间: 2020-02-27 11:43:01

#include<bits/stdc++.h>
using namespace std;

struct node
{
	int l,r,id;
}Q[100005];
long long t=0,l=1,r=0,block,ans[100005],V[100005]={0},a[100005];
bool cmp(node a,node b)
{
	if(a.l/block==b.l/block)return a.r<b.r;
	return a.l/block<b.l/block;
}
void add(int x,int p)
{
	t+=p*a[x]*(2*V[a[x]]+p);
	V[a[x]]+=p;
}
int main()
{
	int i,n,m;
	scanf("%d%d",&n,&m),block=sqrt(n);
	for(i=1;i<=n;i++)scanf("%lld",&a[i]);
	for(i=1;i<=m;i++)scanf("%lld%lld",&Q[i].l,&Q[i].r),Q[i].id=i;
	sort(Q+1,Q+1+m,cmp);
	for(i=1;i<=m;i++)
	{
		while(l<Q[i].l)add(l++,-1);
		while(l>Q[i].l)add(--l,1);
		while(r<Q[i].r)add(++r,1);
		while(r>Q[i].r)add(r--,-1);
		ans[Q[i].id]=t;
	}
	for(i=1;i<=m;i++)printf("%lld\n",ans[i]);
	return 0;
}