有一个长为$a$, 值域为$[1,k]$的序列

对于每个询问区间$[l,r]$

$$
\sum^k_{i=1}{c^2_i}
$$

其中$c_i$表示数字$i$在$[l,r]$中出现的次数

莫队是由前国家队队长莫涛发明的

莫队算法的精髓就是通过合理地对询问排序,然后以较优的顺序暴力回答每个询问。处理完一个询问后,可以使用它的信息得到下一个询问区间的答案。(两个边界瞎跳)

考虑这个问题:对于上面这道题,我们知道区间$[1,5]$的答案,就可以求出$[2,6]$每个数的数量

莫队提供了这样一个排序方案:将原序列以$\sqrt{n}$为一块进行分块(分块的大小也珂以调整),排序第一关键字是询问的左端点所在块的编号,第二关键字是询问的右端点本身的位置,都是升序。然后我们用上面提到的“移动当前区间左右端点”的方法,按顺序求每个询问区间的答案,移动每一个询问区间左右端点可以求出下一个区间的答案。

1
return pos[a.l] == pos[b.l] ? a.r < b.r : pos[a.l] < pos[b.l];

这道题目只要分块排序亿下之后

就可以暴力解决了

1
2
3
4
5
6
7
for (int i = 1; i <= m; i++){
while (q[i].l < l) add(--l);
while (q[i].r > r) add(++r);
while (q[i].l > l) sub(l++);
while (q[i].r < r) sub(r--);
ans[q[i].k] = res;
}

莫队经典片段

更新代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void add(int x) 
{
    cnt[a[x]]++;
    res = res - (cnt[a[x]] - 1) * (cnt[a[x]] - 1) + cnt[a[x]] * cnt[a[x]];
    return;
}

void sub(int x)
{
    cnt[a[x]]--;
    res = res - (cnt[a[x]] + 1) * (cnt[a[x]] + 1) + cnt[a[x]] * cnt[a[x]];
    return;
}

复杂度大约是 $O(n\sqrt{n})$

全部代码

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
#include <bits/stdc++.h>

using namespace std;

#define MAXN 50010

int a[MAXN], cnt[MAXN], pos[MAXN], n, m, k;
long long ans[MAXN], res;
struct Q{
int l, r, k;
}q[MAXN];

void add(int x) {cnt[a[x]]++; res = res - (cnt[a[x]] - 1) * (cnt[a[x]] - 1) + cnt[a[x]] * cnt[a[x]]; return;};
void sub(int x) {cnt[a[x]]--; res = res - (cnt[a[x]] + 1) * (cnt[a[x]] + 1) + cnt[a[x]] * cnt[a[x]]; return;};

bool cmp(Q a, Q b){return pos[a.l] == pos[b.l] ? a.r < b.r : pos[a.l] < pos[b.l];}

int main()
{
#ifndef ONLINE_JUDGE
freopen("in.in", "r", stdin);
freopen("out.out", "w", stdout);
#endif

scanf("%d%d%d", &n, &m, &k);
int siz = sqrt(n);
for (int i = 1; i <= n; i++){
scanf("%d", &a[i]);
pos[i] = i / siz;
}
for (int i = 1; i <= m; i++){
scanf("%d%d", &q[i].l, &q[i].r);
q[i].k = i;
}
sort(q + 1, q + m + 1, cmp);
int l = 2, r = 1;
for (int i = 1; i <= m; i++){
while (q[i].l < l) add(--l);
while (q[i].r > r) add(++r);
while (q[i].l > l) sub(l++);
while (q[i].r < r) sub(r--);
ans[q[i].k] = res;
}
for (int i = 1; i <= m; i++)
printf("%lld\n", ans[i]);
return 0;
}

评论