两个l，r边界转化成四个前缀和式子相加的总和，莫队维护即可。
#include<iostream> #include<cstdio> #include<algorithm> #include<string> #include<cstring> #include<cmath> #include<queue> using namespace std; typedef long long ll; const int N=5e4+10; struct node{ int l,r,id,k;node(){}; node(int _l,int _r,int _id,int _k){ l=_l;r=_r;id=_id;k=_k; } }q[N*4]; int n,m,t,l,r,len,a[N],cntl[N],cntr[N],bl[N];ll res,ans[N]; inline ll read(){ ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();} return x*f; } inline bool operator<(const node&x,const node&y){ return bl[x.l]==bl[y.l]?x.r<y.r:bl[x.l]<bl[y.l]; } inline void addl(){ cntl[a[++l]]++;res+=cntr[a[l]]; } inline void subl(){ res-=cntr[a[l]];cntl[a[l--]]--; } inline void subr(){ res-=cntl[a[r]];cntr[a[r--]]--; } inline void addr(){ cntr[a[++r]]++;res+=cntl[a[r]]; } int main(){ n=read();len=sqrt(n); for(int i=1;i<=n;i++) a[i]=read(),bl[i]=bl[i-1]+((i-1)%len==0); m=read(); for(int i=1;i<=m;i++){ int l1=read(),r1=read(),l2=read(),r2=read(); q[++t]=node(r1,r2,i,1);q[++t]=node(l1-1,l2-1,i,1); q[++t]=node(l1-1,r2,i,-1);q[++t]=node(r1,l2-1,i,-1); } sort(q+1,q+1+t); l=1,r=0; for(int i=1;i<=t;i++){ while(l<q[i].l) addl(); while(l>q[i].l) subl(); while(r>q[i].r) subr(); while(r<q[i].r) addr(); ans[q[i].id]+=1ll*q[i].k*res; } for(int i=1;i<=m;i++) printf("%lld ",ans[i]); return 0; }