LibreOJ 2254 「SNOI2017」一个简单的询问

好久没写过莫队了，今天回来练练手。
其实这题我早就想写了，但是因为鸽子属性咕了很久……
闲来无事，没想到十分钟左右就写完了（

设 f(i,x)=get(1,i,x)。

那么有
get(l1,r1,x)⋅get(l2,r2,x)=(f(r1,x)−f(l1−1,x))⋅(f(r2,x)−f(l2−1,x))=f(r1,x)f(r2,x)−f(r1,x)f(l2−1,x)−f(l1−1,x)f(r2,x)+f(l1−1,x)f(l2−1,x)

那么我们把每个询问 (l1,r1,l2,r2) 都拆成 (r1,r2)−(r1,l2−1)−(l1−1,r2)+(l1−1,l2−1) 的形式。
就能得到 4Q 个只跟两个位置有关的询问。
然后发现询问里面有乘，没法用数据结构维护这个东东。
考虑上莫队。

当然和一般的莫队不同，稍微注意一下就好了。
只要理解了莫队应该都很容易写出来。

代码：

#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
const int N = 5e4;
const int Q = 5e4;
int n,q,a[N + 5],block,pos[N + 5];
int cnt[2][N + 5];
long long cur,ans[Q + 5];
inline void add(int x,int op)
{
    cur -= (long long)cnt[0][a[x]] * cnt[1][a[x]];
    ++cnt[op][a[x]];
    cur += (long long)cnt[0][a[x]] * cnt[1][a[x]];
}
inline void del(int x,int op)
{
    cur -= (long long)cnt[0][a[x]] * cnt[1][a[x]];
    --cnt[op][a[x]];
    cur += (long long)cnt[0][a[x]] * cnt[1][a[x]];
}
struct s_query
{
    int l,r,id,w;
    inline bool operator<(const s_query &o) const
    {
        return pos[l] < pos[o.l] || (pos[l] == pos[o.l] && r < o.r);
    }
} qry[(Q << 2) + 10];
int main()
{
    scanf("%d",&n);
    block = pow(n,2.0 / 3);
    for(register int i = 1;i <= n;++i)
        scanf("%d",a + i),pos[i] = (i - 1) / block + 1;
    scanf("%d",&q);
    int l1,r1,l2,r2;
    for(register int i = 1;i <= q;++i)
    {
        scanf("%d%d%d%d",&l1,&r1,&l2,&r2);
        qry[(i - 1) * 4 + 1] = (s_query){r1,r2,i,1};
        qry[(i - 1) * 4 + 2] = (s_query){r1,l2 - 1,i,-1};
        qry[(i - 1) * 4 + 3] = (s_query){l1 - 1,r2,i,-1};
        qry[i * 4] = (s_query){l1 - 1,l2 - 1,i,1};
    }
    sort(qry + 1,qry + 4 * q + 1);
    for(register int i = 1,l = 0,r = 0;i <= q * 4;++i)
    {
        while(l < qry[i].l)
            add(++l,0);
        while(r < qry[i].r)
            add(++r,1);
        while(l > qry[i].l)
            del(l--,0);
        while(r > qry[i].r)
            del(r--,1);
        ans[qry[i].id] += cur * qry[i].w;
    }
    for(register int i = 1;i <= q;++i)
        printf("%lld\n",ans[i]);
}