【传送门：BZOJ5016】
简要题意：
给出n个数，q个询问，每个询问输入l1,r1,l2,r2，输出$sum_{x=0}^{∞}get(l1,r1,x)*get(l2,r2,x)$
其中$get(l,r,x)$表示l到r中x出现的次数
题解：
看这范围也是要离线的了，莫队搞一波
假设x已经确定，那么设s[i]为前i个数x出现的个数，我们就可以把式子变成(s[r1]-s[l1-1])*(s[r2]-s[l2-1])
然后拆开得到s[r1]*s[r2]-s[l1-1]*s[r2]-s[r1]*s[l2-1]+s[l1-1]*s[l2-1]
然后就变成四项了，把每一项的左右边当作l,r，将一个询问拆成四个询问，分别求值，最后合并在一起就可以了
对于区间改变对答案的影响，假设当前1到l中x(假设x已经确定)出现的次数为s1，1到r中x出现的次数为s2
那么当l向后扩展时（假设扩展的数是x），对答案的贡献为s2，因为(s1+1)*s2-s1*s2=s1，r同理
参考代码：
#include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> using namespace std; typedef long long LL; struct question { int l,r,id; LL f,d; question() { d=0; } }q[210000]; int belong[510000]; int a[510000]; LL s1[510000],s2[510000]; LL sum[510000]; bool cmp(question n1,question n2) { if(belong[n1.l]==belong[n2.l]) return n1.r<n2.r; return belong[n1.l]<belong[n2.l]; } int main() { int n; scanf("%d",&n); int block=int(sqrt(n)); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); belong[i]=(i-1)/block+1; } int Q; 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[4*i-3].l=r1;q[4*i-3].r=r2;q[4*i-3].f=1; q[4*i-2].l=r1;q[4*i-2].r=l2-1;q[4*i-2].f=-1; q[4*i-1].l=l1-1;q[4*i-1].r=r2;q[4*i-1].f=-1; q[4*i].l=l1-1;q[4*i].r=l2-1;q[4*i].f=1; q[4*i-3].id=q[4*i-2].id=q[4*i-1].id=q[4*i].id=i; } sort(q+1,q+4*Q+1,cmp); int l=0,r=0;LL ans=0; for(int i=1;i<=4*Q;i++) { while(r>q[i].r){s2[a[r]]--;ans-=s1[a[r]];r--;} while(r<q[i].r){r++;s2[a[r]]++;ans+=s1[a[r]];} while(l>q[i].l){s1[a[l]]--;ans-=s2[a[l]];l--;} while(l<q[i].l){l++;s1[a[l]]++;ans+=s2[a[l]];} sum[q[i].id]+=q[i].f*ans; } for(int i=1;i<=Q;i++) printf("%lld ",sum[i]); return 0; }