一开始就没打算正解，觉得这种题的数据应该都比较水，就直接以 $l1,r1,l2,r2$ 为关键字排序，竟拿到 $80$ 分。

然后写了个超玄学奇偶优化 cmp，还是 $80$ 分，但快了不少。

inline bool cmp(data x,data y)
{
	if(b[x.l1]==b[y.l1])
	{
		if(b[x.r1]==b[y.r1])
		{
			if(b[x.l2]==b[y.l2])
			{
				if(b[x.l2]&1) return x.r2<y.r2;
				return x.r2>y.r2;
			}
			if(b[x.r1]&1) return b[x.l2]<b[y.l2];
			return b[x.l2]>b[y.l2];
		}
		if(b[x.l1]&1) return b[x.r1]<b[y.r1];
		return b[x.r1]>b[y.r1];
	}
	return b[x.l1]<b[y.l1];
}

然后把块长改为 $1000$，就 A 了？！

完整 AC 代码：

#include <bits/stdc++.h>
#define ll long long
#define rll register ll
#define cll const ll
#define N 50005
using namespace std;
inline ll read()
{
    rll x=0;bool f=1;register char c=getchar();
    while(c<48||c>57){if(c=='-') f=0;c=getchar();}
    while(c>=48&&c<=57){x=x*10+(c^48);c=getchar();}
    return f?x:-x;
}
inline void write(ll x)
{
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+48);
}
cll n=read(),L=1000;
ll m,now,a[N],b[N],bl[N],br[N],ans[N],cnt1[N],cnt2[N];
struct data{ll l1,r1,l2,r2,id;}q[N];
inline bool cmp(data x,data y)
{
	if(b[x.l1]==b[y.l1])
	{
		if(b[x.r1]==b[y.r1])
		{
			if(b[x.l2]==b[y.l2])
			{
				if(b[x.l2]&1) return x.r2<y.r2;
				return x.r2>y.r2;
			}
			if(b[x.r1]&1) return b[x.l2]<b[y.l2];
			return b[x.l2]>b[y.l2];
		}
		if(b[x.l1]&1) return b[x.r1]<b[y.r1];
		return b[x.r1]>b[y.r1];
	}
	return b[x.l1]<b[y.l1];
}
inline void add1(ll x)
{
	now-=cnt1[x]*cnt2[x];
	cnt1[x]++;
	now+=cnt1[x]*cnt2[x];
}
inline void del1(ll x)
{
	now-=cnt1[x]*cnt2[x];
	cnt1[x]--;
	now+=cnt1[x]*cnt2[x];
}
inline void add2(ll x)
{
	now-=cnt1[x]*cnt2[x];
	cnt2[x]++;
	now+=cnt1[x]*cnt2[x];
}
inline void del2(ll x)
{
	now-=cnt1[x]*cnt2[x];
	cnt2[x]--;
	now+=cnt1[x]*cnt2[x];
}
int main()
{
    for(rll i=1;i<=n;i++)
    	a[i]=read(),b[i]=(i-1)/L+1;
    m=read();
    for(rll i=1;i<=m;i++)
    {
    	q[i].l1=read(),q[i].r1=read();
    	q[i].l2=read(),q[i].r2=read();
    	q[i].id=i;
	}
	sort(q+1,q+m+1,cmp);
	for(rll i=1,l1=1,r1=0,l2=0,r2=0;i<=m;i++)
	{
		while(l1>q[i].l1) add1(a[--l1]);
		while(r1<q[i].r1) add1(a[++r1]);
		while(l1<q[i].l1) del1(a[l1++]);
		while(r1>q[i].r1) del1(a[r1--]);
		while(l2>q[i].l2) add2(a[--l2]);
		while(r2<q[i].r2) add2(a[++r2]);
		while(l2<q[i].l2) del2(a[l2++]);
		while(r2>q[i].r2) del2(a[r2--]);
		ans[q[i].id]=now;
	}
	for(rll i=1;i<=m;i++)
		write(ans[i]),putchar('\n');
    return 0;
}

求巨佬鉴定复杂度。