CF Strange Queries（莫队+容斥好题）

题面戳这里

（这几天做莫队要做吐了啊……从数列找不同到小B的询问，HH 的项链，异或序列，小z的袜子，到这道题，感觉终于开始觉得所谓“莫队题长得都一样“了）

CF上AC代码一份：

#include<bits/stdc++.h>
using namespace std;
#define N 50005
#define ll long long
int n,m,a[N],len,cnt[N];
ll now,ans;
struct la{
    int l,r,id,blo; 
    ll x;
    la(int l=0,int r=0,int id=0,int blo=0,ll x=0):l(l),r(r),id(id),blo(blo),x(x){}
}ask[N<<2];
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
bool cmp1(la x,la y){if(x.blo==y.blo)return x.r<y.r;return x.blo<y.blo;}
bool cmp2(la x,la y){return x.id<y.id;}
inline void move(int p,int f){
    now-=1ll*(cnt[a[p]]-1)*cnt[a[p]]/2;
    cnt[a[p]]+=f;
    now+=1ll*(cnt[a[p]]-1)*cnt[a[p]]/2;
}
int main(){
    n=read();for(int i=1;i<=n;++i)a[i]=read();
    m=read();len=sqrt(n);
    for(int i=1,b,c,d,e;i<=m;i++){
        b=read(),c=read(),d=read(),e=read();c++,d--;//为了保证c,d位置的值不会被去掉
        ask[4*i-3]=la(b,e,4*i-3,(b-1)/len+1);
        ask[4*i-2]=la(b,d,4*i-2,(b-1)/len+1);
        ask[4*i-1]=la(c,e,4*i-1,(c-1)/len+1);
        ask[4*i]=la(c,d,4*i,(c-1)/len+1);
    }
    sort(ask+1,ask+4*m+1,cmp1);
    int l=1,r=0;
    for(int i=1;i<=4*m;i++){
        while(l<ask[i].l)move(l++,-1);
        while(l>ask[i].l)move(--l,1);
        while(r<ask[i].r)move(++r,1);
        while(r>ask[i].r)move(r--,-1);
        ask[i].x=now;
    //    printf("%d %d %lld\n",l,r,now);
    }
    sort(ask+1,ask+4*m+1,cmp2);
    for(int i=1;i<=4*m;i+=4){
        ans=ask[i].x-ask[i+1].x-ask[i+2].x+ask[i+3].x;//容斥
        printf("%lld\n",ans);
    }
    return 0;
}