【学习笔记】简单莫队瞎吹

…感觉这东西似乎也没啥好说的啊

$1$ 理论瞎吹

大概就是个分块?但是是对询问分块的。莫队的精髓在于排序,排序时如果 belong[l] 相同复杂度就按照右端点排序,这样似乎是有保证的?

令 $m$ 为操作数,$B$ 为块大小。考虑对于一个块内的 $l$,其 $r$ 是单增的,于是考虑如下:

  • 左端点,在块内可能会一前一后这样设置,这样复杂度被卡到最满,为 $O(m\cdot B)$ ;
  • 右端点,考虑各块内的询问显然都可以做到单块 $O(n)$,所以不需要考虑 $m$ 的贡献,即右端点移动的复杂度就是 $\frac{n}{B}\cdot n=\frac{n^2}{B}$。

均值一下发现 $m\cdot B+\frac{n^2}{B}\geq 2\sqrt{n^2m}=O(n\sqrt m)$ ,此时有 $m\cdot B=\frac{n^2}{B}$,解得 $B=\frac{n}{\sqrt m}$ .

所以取块大小为 $\frac{n}{\sqrt m}$ 时达到理论最优,复杂度为 $O(n\sqrt m)$ 。

…当然这东西可能不准,毕竟常数稍微优一点可能就可以瞎分块了233

然后考虑如何带修改(当然只能离线做)。发现单纯地平移询问区间不对,于是考虑加一维时间轴,在平移完询问之后平移修改操作。排序时把「离当前询问最近的前一个修改操作是第几次修改」作为第三关键字,第二关键字换成「右端点所在块的编号」。

令 $c$ 为修改个数, $q$ 为询问个数,$B$ 依旧为块大小。那么考虑三维指针是怎么移动的:

  • 左端点和右端点依次还是 $qB+\frac{n^2}{B}$ ;
  • 时间端点,考虑时间端点实际上每次至多移动 $c$,但是时间端点之外此时套了一层按 belong[r] 分的块,所以这一部分的复杂度为 $O(c\times\frac{n^2}{B^2})$ .

于是总复杂度为 $O(\frac{n^2c}{B^2}+qB+\frac{n^2}{B})$。

这个东西他怎么求 $\min$ 呢…

嗯,你看这个式子这么可爱,求导总是可以求出来的吧,于是就不详细写了~

直接上结论,$B=O(n^{\frac{2}{3}})$ 时最优,此时复杂度为 $O(n^{\frac{2}{3}}c+n^{\frac{2}{3}}q+n^\frac{4}{3})=O(n^{\frac{2}{3}}m)$。

发现这东西很好的一点就是,这么分块,复杂度不会受操作类型影响,因为 $q+c=m$ 是根据已知推出来,不是放缩放掉的。所以是个很满分的复杂度。

$2$ 水题瞎做

$1$ LG2709 小B的询问

给出长度为 $n$ 的序列,$q$ 组询问,每次询问区间 $[l,r]$ 内的 $\sum e_i^2$ 。其中 $e_i$ 表示数 $i$ 的出现次数。

似乎是憨憨题?就是道普通的莫队。

不过学了一招,就是奇偶块的 $r$ 坐标反向排序。这样似乎理论应该带一个下界为 $\frac{1}{2}$ 的常数。但实际应用可能并不明显。

1
2
3
4
5
il bool comp(querys a, querys b){
return blg[a.l] == blg[b.l] ? ((blg[a.l] & 1) ? a.r < b.r : a.r > b.r) : blg[a.l] < blg[b.l] ;
}
il void del(int p){ ans -= (2ll * buc[base[p]] - 1ll), buc[base[p]] -- ; }
il void add(int p){ ans += (2ll * buc[base[p]] + 1ll), buc[base[p]] ++ ; }

$2$ LG1494 小Z的袜子

给出一个长为 $n$ 的序列,每次询问 $[l,r]$ 内,随机取两个数取到相同的数的概率。

大概也是个憨憨题…发现最后结果就是 $\frac{\mathrm{cnt(same\_pair)}}{\binom{r-l+1}{2}}$。

$3$ LG3709 大爷的字符串题

这题nmd是道语文题…

原题面:

给你一个字符串 $a$,每次询问一段区间的贡献

贡献定义:

每次从这个区间中拿出一个字符 $x$,然后把 $x$ 从这个区间中删除,你要维护一个集合 $\rm S$:如果 $\rm S$ 为空,你 $rp$ 减 $1$ ; 如果 $\rm S$ 中有一个元素不小于 $x$,则你 $rp$ 减 $1$,清空 $\rm S$;之后将 $x$ 插入 $\rm S$ 。

由于你是大爷,平时做过的题考试都会考到,所以每次询问你搞完这段区间的字符之后最多还有多少 $rp$ ?$rp$ 初始为 $0$,询问之间不互相影响。

发现大概是在说,每次给定一个区间,要从中取出最少数量的严格上升子序列使得覆盖所有的数。发现其实就是「区间内出现次数最多的数」出现的次数。

这东西也比较容易维护,再拿另一个 $bucbuc$ 来维护 $buc$ 就解决了。

1
2
3
4
5
6
7
8
il void add(const int &p){ 
rg int t = ++ buc[base[p]] ;
bucbuc[t] ++, bucbuc[t - 1] --, ans += (t > ans) ;
}
il void del(const int &p){
rg int t = -- buc[base[p]] ;
bucbuc[t] ++, bucbuc[t + 1] --, ans -= !bucbuc[ans] ;
}

这是离散化之后的,复杂度就是比较稳的 $m \sqrt n$ 了。

但是还有一个不费脑子的方法,就是第一个 $buc$ 直接用 std:: unordered_map 来实现。但这东西首先复杂度是个谜,你说他是 $O(1)$ 的,但是确实很慢;你说他是 $\log$ 的,但毕竟只是个 $Hash$ 表,实在没理由是 $\log$ 的。

嗯,具体实现可能是什么 「亚 $\log$」 的Hash表吧。

$4$ LG1903 [国家集训队]数颜色

询问区间内不同的数的个数+带修。

这有啥好说的啊?

不过有一点需要注意:由于时间轴左右横跳要消除贡献,所以需要记录一下每个位置修改之前的值。这个地方直接 std:swap 做就好了。

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
il bool comp(querys a, querys b){
return blg[a.l] == blg[b.l] ?
(blg[a.r] == blg[b.r] ? a.t < b.t : blg[a.r] < blg[b.r]) : blg[a.l] < blg[b.l] ;
}
il void del(int p){ if (!-- buc[base[p]]) -- ans ; }
il void add(int p){ if (!buc[base[p]] ++) ++ ans ; }
int main(){
cin >> N >> M ; int l, r, v, p, i, j ;
for (i = 1 ; i <= N ; ++ i) scanf("%d", &base[i]) ;
for (i = 1 ; i <= M ; ++ i){
scanf("%s", In + 1) ;
if (In[1] == 'Q')
scanf("%d%d", &l, &r), q[++ cntq].t = cntm,
q[cntq].l = l, q[cntq].r = r, q[cntq].id = cntq ;
else scanf("%d%d", &p, &v), m[++ cntm].p = p, m[cntm].c = v ;
}
B = pow((double)N, 0.677),
Bnum = ceil((double)N / (double)B) ;
for (i = 0 ; i < Bnum ; ++ i)
for (j = B * i + 1 ; j <= B * (i + 1) ; ++ j) blg[j] = i + 1 ;
l = 1, r = 0, ans = 0, T = 0 ;
sort(q + 1, q + cntq + 1, comp) ;
for (i = 1 ; i <= M ; ++ i){
while (l < q[i].l) del(l ++) ;
while (l > q[i].l) add(-- l) ;
while (r > q[i].r) del(r --) ;
while (r < q[i].r) add(++ r) ;
while (q[i].t > T){
++ T ;
if (m[T].p <= q[i].r && m[T].p >= q[i].l){
if (!-- buc[base[m[T].p]]) -- ans ;
if (!buc[m[T].c] ++) ++ ans ;
}
swap(m[T].c, base[m[T].p]) ;
}
while (q[i].t < T){
if (m[T].p <= q[i].r && m[T].p >= q[i].l){
if (!-- buc[base[m[T].p]]) -- ans ;
if (!buc[m[T].c] ++) ++ ans ;
}
swap(m[T].c, base[m[T].p]) ;
-- T ;
}
res[q[i].id] = ans ;
}
for (i = 1 ; i <= cntq ; ++ i) printf("%d\n", res[i]) ;
return 0 ;
}

似乎选的都是很水的…剩下的题需要脑子,我莫得脑子,所以就先这样吧。