For problems with queries of the form (L,R) that can be transformed between queries to find the answer, we can use the Mo Algorithm by sorting the queries as follows:
// Time complexity: (N+Q)*sqrt(N)*k
// (k is time complexity of the add & del functions)
// value of "id" is from 1-n
struct query
{
int l, r, id;
};
query q[maxn];
int s = sqrt(n);
bool cmp(query a,query b)
{
if((a.l+s-1)/s!=(b.l+s-1)/s){
return (a.l+s-1)/s<(b.l+s-1)/s;
}
return a.r<b.r;
}
// Solution by Tien Minh
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pp push_back
#define all(x) (x).begin(),(x).end()
using namespace std;
using ll = long long;
const char el ='\n';
const ll maxn = 1e6+5, mod = 1e9+7;
ll n,t,s,a[maxn],mark[maxn];
ll ans[maxn],num;
struct query
{
int l, r, id;
};
query q[maxn];
bool cmp(query a,query b)
{
if((a.l+s-1)/s!=(b.l+s-1)/s){
return (a.l+s-1)/s<(b.l+s-1)/s;
}
return a.r<b.r;
}
void add(ll x)
{
num=num-mark[x]*mark[x]*x;
++mark[x];
num=num+mark[x]*mark[x]*x;
}
void del(ll x)
{
num=num-mark[x]*mark[x]*x;
--mark[x];
num=num+mark[x]*mark[x]*x;
}
void input()
{
cin>>n>>t;
s=sqrt(n);
for(int i=1;i<=n;++i) cin>>a[i];
for(int i=1;i<=t;++i)
{
cin>>q[i].l>>q[i].r;
q[i].id=i;
}
sort(q+1,q+t+1,cmp);
int l=1,r=0;
for(int i=1;i<=t;++i)
{
while(r<q[i].r)
{
++r;
add(a[r]);
}
while(r>q[i].r)
{
del(a[r]);
--r;
}
while(l>q[i].l)
{
--l;
add(a[l]);
}
while(l<q[i].l)
{
del(a[l]);
++l;
}
ans[q[i].id]=num;
}
for(int i=1;i<=t;++i) cout<<ans[i]<<el;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
input();
return 0;
}