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

发表于 | 分类于 |

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

设 \(f(i,x) = \text{get}(1,i,x)\)。

那么有
\[\begin{eqnarray} & & \text{get}(l_1,r_1,x) \cdot \text{get}(l_2,r_2,x) \\ & = & (f(r_1,x) - f(l_1 - 1,x)) \cdot (f(r_2,x) - f(l_2 - 1,x)) \\ & = & f(r_1,x)f(r_2,x) - f(r_1,x)f(l_2 - 1,x) - f(l_1 - 1,x)f(r_2,x) + f(l_1 - 1,x)f(l_2 - 1,x) \end{eqnarray}\]

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

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

代码： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#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]);
}