Luogu

LOJ

分析

$$
\begin{aligned} \sum_{i=0}^{\infty} get(l_1, r_1, x) \times get(l_2, r_2, x) = &\sum_{i=0}^{\infty} get(0, r_1, x) \times get(0, r_2, x)\\ - &\sum_{i=0}^{\infty} get(0, l_1-1, x) \times get(0, r_2, x)\\ - &\sum_{i=0}^{\infty} get(0, r_1, x) \times get(0, l_2-1, x) \\ + &\sum_{i=0}^{\infty} get(0, l_1-1, x) \times get(0, l_2-1, x) \end{aligned}
$$

这样子就可以把每个询问拆成四个，然后莫队即可。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
typedef long long ll;
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=50000+10;

int a[N],tot=0,block;
struct query { int l,r,id,op; } q[N<<2];
ll Ans[N],ans;
int cntl[N],cntr[N];

inline int cmp(query a,query b) {
    if (a.l/block!=b.l/block) return a.l<b.l;
    else if ((a.l/block)&1) return a.r<b.r;
    else return a.r>b.r;
}

inline void addl(int x) { ++cntl[x],ans+=cntr[x]; }
inline void dell(int x) { ans-=cntr[x],--cntl[x]; }
inline void addr(int x) { ++cntr[x],ans+=cntl[x]; }
inline void delr(int x) { ans-=cntl[x],--cntr[x]; }

int main() {
    int n=read(); block=sqrt(n);
    for (re int i=1;i<=n;++i) a[i]=read();
    int Q=read();
    for (re int i=1;i<=Q;++i) {
        int l1=read(),r1=read(),l2=read(),r2=read();
        q[++tot]=(query){r1,r2,i,1};
        q[++tot]=(query){l1-1,r2,i,-1};
        q[++tot]=(query){r1,l2-1,i,-1};
        q[++tot]=(query){l1-1,l2-1,i,1};
    }
    sort(q+1,q+tot+1,cmp);
    int l=0,r=0;
    for (re int i=1;i<=tot;++i) {
        while (l<q[i].l) addl(a[++l]);
        while (l>q[i].l) dell(a[l--]);
        while (r<q[i].r) addr(a[++r]);
        while (r>q[i].r) delr(a[r--]);
        Ans[q[i].id]+=q[i].op*ans;
    }
    for (re int i=1;i<=Q;++i) printf("%lld\n",Ans[i]);
    return 0;
}