a数组大小为n。(1 ≤ n ≤ 50 000) (1 ≤ q ≤ 50 000)(1 ≤ ai ≤ n) q个查询,询问两个区间相同的数有多少对。
#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;
}