【 Gym - 101138D 】Strange Queries （莫队算法）

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cmath>
#define N 50005
#define ll long long
using namespace std;
int n,m,a[N],qs,pos[N];
ll ans[N],s[N];
struct node{int l,r,d;}p[N<<2];
bool cmp(node a,node b){
	return pos[a.l]<pos[b.l]||pos[a.l]==pos[b.l]&&a.r<b.r;
}
void add(int p,ll &f){
	f+=s[a[p]]++;
}
void sub(int p,ll &f){
	f-=--s[a[p]];
}
int main() {
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	for(int i=1,j=1;i<=n;i++){
		if(i%(int)sqrt(n)==0)j++;
		pos[i]=j;
	}
	scanf("%d",&qs);
	for(int i=1;i<=qs;i++){
		int sl,sr,tl,tr;
		scanf("%d%d%d%d",&sl,&sr,&tl,&tr);
		sr++;tl--;
		//[sl,tr]-[sl,tl-1]-[sr+1,tr]+[sr+1,tl-1]
		p[m++]=(node){sl,tr,i};p[m++]=(node){sl,tl,-i};
		p[m++]=(node){sr,tr,-i};p[m++]=(node){sr,tl,i};
	}
	sort(p,p+m,cmp);
	int L=n+1,R=n;
	ll num=0;
	for(int i=0;i<m;i++){
		while(L<p[i].l)
			sub(L++,num);
		while(L>p[i].l)
			add(--L,num);
		while(R>p[i].r)
			sub(R--,num);
		while(R<p[i].r)
			add(++R,num);
		if(p[i].d>0)ans[p[i].d]+=num;
		else ans[-p[i].d]-=num;
	}
	for(int i=1;i<=qs;i++)printf("%lld\n",ans[i]);
	return 0;
}