正题

题目链接:https://www.luogu.com.cn/problem/P5268

---

题目大意

$n$个数的一个序列，定义$get(l_1,r_1,x)$表示区间$[l_1,r_1]$中有多少个$x$。

每次询问$(l_1,r_1,l_2,r_2)$求$$\sum _x^{\infty }get(l_1,r_1,x)\ast get(l_2,r_2,x)$$

---

解题思路

考虑莫队，有$$get(l_1,r_1,x)\ast get(l_2,r_2,x)$$

$$=$$

$$get(1,r_1,x)\ast get(1,r_2,x)-get(1,l_1-1,x)\ast get(1,r_2,x)$$$$-get(1,r_1,x)\ast get(1,l_2-1,x)+get(1,l_1-1,x)\ast get(1,l_2-1,x)$$

然后分成四次莫队就好了

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #include<cmath> using namespace std; const int N=5e4+10; struct node{ int l,r,id,w; }q[N*4]; int n,cnt,T,Q,a[N],ans[N],v1[N],v2[N]; bool cmp(node x,node y) {return x.l/T<y.l/T||(x.l/T==y.l/T&&x.r<y.r);} int main() { scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); T=sqrt(n); scanf("%d",&Q); for(int i=1;i<=Q;i++){ int l1,r1,l2,r2; scanf("%d%d%d%d",&l1,&r1,&l2,&r2); q[++cnt]=(node){r1,r2,i,1}; q[++cnt]=(node){r1,l2-1,i,-1}; q[++cnt]=(node){l1-1,r2,i,-1}; q[++cnt]=(node){l1-1,l2-1,i,1}; } sort(q+1,q+1+cnt,cmp); int l=0,r=0,val=0; for(int i=1;i<=cnt;i++){ while(r<q[i].r)++r,v2[a[r]]++,val+=v1[a[r]]; while(r>q[i].r)v2[a[r]]--,val-=v1[a[r]],r--; while(l<q[i].l)++l,v1[a[l]]++,val+=v2[a[l]]; while(l>q[i].l)v1[a[l]]--,val-=v2[a[l]],l--; ans[q[i].id]+=q[i].w*val; } for(int i=1;i<=Q;i++) printf("%d\n",ans[i]); }