题目大意：

给你一个长度为\(N\)的数列，求满足\(a_i = a_j\)且\(l1\leq i \leq r1 , l2 \leq j \leq r2\)的\((i,j)\)对数。

看到这种题目，第一反应就是莫队啦，但一看这个询问有点奇怪，不好算，怎么办呢？

这个时候就要用到容斥原理了

至于怎么容斥，学过容斥原理的就可以跳过了。

首先：我们要求的答案一定在\([l1,r2]\)(假设\(r1 < r2\))区间之内。很明显我们在这个区间内有许多答案是不需要的，那么就需要减去，比如\([l1,r1]\)自己配对或\([l1,r1]\)与\([r1,l2]\)的配对，减去这些之后，我们发现区间\([r1,l2]\)会被减去两次，所以要加上来。

然后，我们就得到了美丽的关系式：

\[ Ans = ans[l1,r2] - ans[l1,l2] - ans[r1,r2] + ans[r1,l2] \]

为了保证复杂度，我们要把四个$ ans $放在四个询问中，所以要开四倍。

\(\mathcal{Code}\)：

#include
    
     #include
     
      #include
      
       #include
       
        #define get ch=getchar()#define isd (ch>=48&&ch<=57)#define ll long long#define Re register#define In inlineusing namespace std;const int maxn=5e5+1;In int read(){    char get;int r=0,s=1;    while(!isd)s=ch==45?0:s,get;while(isd)r=(r<<1)+(r<<3)+(ch^48),get;    return s?r:-r;}struct Q{int l,r,id;}q[maxn<<2];int n,m,M,u,L,R;ll Ans;int a[maxn],pos[maxn];ll ans[maxn],s[maxn];bool cmp(Q a,Q b){return pos[a.l]==pos[b.l]?a.r
        
         
          q[i].l)add(--L); while(R>q[i].r)sub(R--); while(R
          
           0)ans[q[i].id]+=Ans; else ans[-q[i].id]-=Ans; } for(int i=1;i<=M;i++)printf("%lld\n",ans[i]); return 0;}