Steven_Meng's Blog

传送门

给你一个序列$\{a_i\}$，和四个数$l1,r1,l2,r2$，求区间$[l1,r1]，[l2,r2]$中相同的数有多少对。

当然你不能维护四个指针，考虑容斥原理，我们不妨设$f(x,y)$为下标为$[1,x]$和下标为$[1,y]$中相同的$a_i$有多少对，这样我们可以开心地容斥$Query(l1,r1,l2,r2)=f(l2,r2)-f(l1-1,r2)-f(r1,l2-1)+f(l1-1,l2-1)$。

具体实现的时候，$Query$结构体里面存一个$f$代表符号即可。

#include <bits/stdc++.h>
#define MAXN 100005
using namespace std;
inline int read(){
    int 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<<3)+(x<<1)+(ch^'0');
        ch=getchar();
    }
    return x*f;
}
int a[MAXN],Ans[MAXN],cnt1[MAXN],cnt2[MAXN],qcnt,pos[MAXN];
struct Query{
    int pos1,pos2;//代表的是[1,pos1]，[1,pos2]
    int id,f;//容斥的符号
}Q[MAXN*4];
inline bool operator < (const Query &a,const Query &b){
    return pos[a.pos1]<pos[b.pos1]||(pos[a.pos1]==pos[b.pos1]&&((pos[a.pos1]&1)?a.pos2<b.pos2:a.pos2>b.pos2));
}
inline void AddQuery(int pos1,int pos2,int id,int f){
    Q[++qcnt].f=f,Q[qcnt].id=id,Q[qcnt].pos1=pos1,Q[qcnt].pos2=pos2;
}
int main(){
    int n=read(),m=read();
    int Size=sqrt(n);
    for (register int i=1;i<=n;++i){
        a[i]=read();
        pos[i]=(i-1)/Size+1;
    }
    for (register int i=1;i<=m;++i){
        int l1=read(),r1=read(),l2=read(),r2=read();
        AddQuery(r1,r2,i,1);
        AddQuery(l1-1,r2,i,-1);
        AddQuery(r1,l2-1,i,-1);
        AddQuery(l1-1,l2-1,i,1);
    }
    sort(Q+1,Q+1+qcnt);
    int r1=0,r2=0,ans=0;
    for (register int i=1;i<=qcnt;++i){
        while (r1<Q[i].pos1){
            ++cnt1[a[++r1]];
            ans+=cnt2[a[r1]];
        }
        while (r1>Q[i].pos1){
            --cnt1[a[r1]];
            ans-=cnt2[a[r1--]];
        }
        while (r2<Q[i].pos2){
            ++cnt2[a[++r2]];
            ans+=cnt1[a[r2]];
        }
        while (r2>Q[i].pos2){
            --cnt2[a[r2]];
            ans-=cnt1[a[r2--]];
        }
        Ans[Q[i].id]+=Q[i].f*ans;
    }
    for (register int i=1;i<=m;++i){
        printf("%d\n",Ans[i]);
    }
}