[SNOI2017]一个简单的询问

题目大意：

给定一个长度为\(n(n\le50000)\)的序列\(A(1\le A_i\le n)\)，定义\(\operatorname{get}(l,r,x)\)为区间\(A_{[l,r]}\)中\(x\)的出现次数。\(m(m\le50000)\)次询问，每次给出\(l_1,r_1,l_2,r_2\)，求\(\sum_{x=0}^{\infty}\operatorname{get}(l_1,r_1,x)\cdot\operatorname{get}(l_2,r_2,x)\)。

思路：

\[ \operatorname{ans}(l_1,r_1,l_2,r_2)=\operatorname{ans}(1,r_1,1,r_2)-\operatorname{ans}(1,l_1-1,1,r_2)-\operatorname{ans}(1,r_1,1,l_2-1)+\operatorname{ans}(1,l_1-1,1,l_2-1) \]

因此将每组询问拆成\(4\)个，然后直接套用莫队算法即可。

时间复杂度\(\mathcal O(n\sqrt n)\)。

源代码：

#include<cmath>
#include<cstdio>
#include<cctype>
#include<algorithm>
inline int getint() {
    register char ch;
    while(!isdigit(ch=getchar()));
    register int x=ch^'0';
    while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');
    return x;
}
typedef long long int64;
const int N=5e4+1,M=5e4;
int n,a[N],block,cnt[2][N];
int64 tmp,ans[M];
struct Query {
    int p0,p1,id,type;
    bool operator < (const Query &rhs) const {
        if(p0/block==rhs.p0/block) return p1<rhs.p1;
        return p0/block<rhs.p0/block;
    }
};
Query q[M*4];
inline void ins(const bool &t,const int &x) {
    tmp-=(int64)cnt[0][x]*cnt[1][x];
    cnt[t][x]++;
    tmp+=(int64)cnt[0][x]*cnt[1][x];
}
inline void del(const bool &t,const int &x) {
    tmp-=(int64)cnt[0][x]*cnt[1][x];
    cnt[t][x]--;
    tmp+=(int64)cnt[0][x]*cnt[1][x];
}
int main() {
    block=sqrt(n=getint());
    for(register int i=1;i<=n;i++) a[i]=getint();
    const int m=getint();
    int tot=0;
    for(register int i=0;i<m;i++) {
        const int l1=getint(),r1=getint(),l2=getint(),r2=getint();
        q[tot++]=(Query){r1,r2,i,1};
        if(l2>1) q[tot++]=(Query){r1,l2-1,i,-1};
        if(l1>1) q[tot++]=(Query){l1-1,r2,i,-1};
        if(l1>1&&l2>1) q[tot++]=(Query){l1-1,l2-1,i,1};
    }
    std::sort(&q[0],&q[tot]);
    for(register int i=0,p0=0,p1=0;i<tot;i++) {
        while(p0<q[i].p0) ins(0,a[++p0]);
        while(p1<q[i].p1) ins(1,a[++p1]);
        while(p0>q[i].p0) del(0,a[p0--]);
        while(p1>q[i].p1) del(1,a[p1--]);
        ans[q[i].id]+=tmp*q[i].type;
    }
    for(register int i=0;i<m;i++) {
        printf("%lld\n",ans[i]);
    }
    return 0;
}

[SNOI2017]一个简单的询问

原文：https://www.cnblogs.com/skylee03/p/9767014.html