莫队板

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+10;
int a[N],ans[N],cnt[N],B,mq,mr,sum;
struct node{int l,r,id;}q[N];
bool cmp(node n1,node n2){return n1.l/B!=n2.l/B?n1.l<n2.l:n1.r<n2.r;}
void add(int x)
{
	sum+=(cnt[x])*(cnt[x]-1)/2;
	cnt[x]++;
}
void del(int x)
{
	cnt[x]--;
	sum-=(cnt[x])*(cnt[x]-1)/2;
}
signed main()
{
	int n,m;cin>>n>>m;B=sqrt(n);
	for(int i=1;i<=n;i++)cin>>a[i];
	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);
	for(int i=1,l=1,r=0;i<=m;i++)
	{
		while(l>q[i].l)add(a[--l]);
		while(r<q[i].r)add(a[++r]);
		while(l<q[i].l)del(a[l++]);
		while(r>q[i].r)del(a[r--]);
		ans[q[i].id]=sum;
	}
	for(int i=1;i<=m;i++)cout<<ans[i]<<'\n';
	return 0;
}