Description

给你一个长度为N的序列ai，1≤i≤N和q组询问，每组询问读入l1,r1,l2,r2，需输出

get(l,r,x)表示计算区间[l,r]中，数字x出现了多少次。

Input

第一行，一个数字N，表示序列长度。

第二行，N个数字，表示a1～aN

第三行，一个数字Q，表示询问个数。

第4～Q+3行，每行四个数字l1,r1,l2,r2，表示询问。

N,Q≤50000

N1≤ai≤N

1≤l1≤r1≤N

1≤l2≤r2≤N

注意：答案有可能超过int的最大值

Output

对于每组询问，输出一行一个数字，表示答案

Sample Input

5

1 1 1 1 1

2

1 2 3 4

1 1 4 4

Sample Output

4

1

分析：

哦，mf

我们又要开始画柿子了：

我们先把l都减一，这样我们get(l,r,x)就可以转化为

get(1,r,x)-get(1,l,x)

令是s(i)=get(1,i,x)

在其他网站上看到的乱码，复制到自己的博客里，就变成了这么nb的柿子！！！

ans=∑x(s(r1)−s(l1))∗(s(r2)−s(l2)))=∑xs(r1)∗s(r2)+s(l1)∗s(l2)−s(l1)∗s(r2)−s(r1)∗s(l2)注释∗∗ab=(a+b)2−a2−b22∗∗=∑xs(r1)2+s(r2)2−(s(r2)−s(r1))2+s(l1)2+s(l2)2−(s(l2)−s(l1))2+(s(r2)−s(l1))2−s(r2)2−s(l1)2+(s(r1)−s(l2))2−s(r1)2−s(l2)22=∑x(s(r1)−s(l2))2+(s(r2)−s(l1))2−(s(l2)−s(l1))2−(s(r2)−s(r1))22

盯着这个柿子，我感到了阵阵寒意。。。

仔细看分子，实际上就是四个区间中x的数量的平方

(r1,l2),(l1,r2),(l1,l2),(r1,r2)

我们只需要用莫队维护一下区间x的个数的平方就可以了

然而我们在用莫队暴力转移的时候，

每次最多减1，由x^2—->(x-1)^2

所以在统计答案的时候，只用加减2*x-1

这里写代码片#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #define ll long longusing namespace std;const int N=50001;ll s[50002],sum=0;int n,Q;ll a[50002],ans[N];struct node{    int l1,l2,r1,r2;};node q[50002];int tot=0;struct nd{    int x,y,org,k;};nd kuai[N<<2];int unit;int cmp(const nd &a,const nd &b){    if (a.x/unit==b.x/unit) return a.y
          
           kuai[i].x) l--,s[a[l]]++,sum+=2*s[a[l]]-1; while (l
           
            kuai[i].y) sum-=2*s[a[r]]-1,s[a[r]]--,r--; ans[kuai[i].org]+=kuai[i].k*sum; }}int main(){ scanf("%d",&n); for (int i=1;i<=n;i++) scanf("%lld",&a[i]); unit=(int)sqrt(n); scanf("%d",&Q); for (int i=1;i<=Q;i++) { scanf("%d%d%d%d",&q[i].l1,&q[i].r1,&q[i].l2,&q[i].r2); q[i].l1--; q[i].l2--; put(q[i].l1,q[i].l2,i,-1); put(q[i].r1,q[i].r2,i,-1); put(q[i].l1,q[i].r2,i,1); put(q[i].r1,q[i].l2,i,1); } sort(kuai+1,kuai+4*Q+1,cmp); doit(); for (int i=1;i<=Q;i++) printf("%lld\n",ans[i]>>1); //最后要除以2 return 0;}