莫队

窝的莫队学习笔记,可以配合食用

我会对于难度进行一个评分,可以按照难度大小来做。

普通莫队

P1494

莫队模板题。在文章中有对普通莫队的介绍。

评分:2,毕竟是板子题。

P5268

需要再推一些式子而已,但是也不难。是一道不错的练手题。

评分:3,难度不大。

P4396

稍微有点进阶了。还需要用到值域分块,

评分:4,难度还是有的。

P7708

比较另类的题目。思维难度和代码难度都比前两题高。

评分:6,难度不能算非常大,但是做出了这题,基础莫队基本是过关了。

带修莫队

引言:
虽然莫队是离线算法,但是还是可以修改的,但是这个东西还是比较少见的。

P1903

虽然莫队是离线的,但是还是有修改的操作!!这是一道板子题。

评分:4,这个东西还是比普通莫队难许多的。

当然这一类题目比较少见,还有一道例题在后面,放在后面是因为需要使用树上莫队。

回滚莫队

引言:
代码难度上了一个调节,而且需要谨慎甄别两种不同的回滚莫队。

AT_joisc2014_c

回滚莫队例题。详细的写法靠我的博客。

评分:5 分。

P5906

虽然是模板题,但是难度比上面的那个高许多。但是这一类的东西还是很少见的。

评分:6 分。

P8530

回滚莫队+二维分块,这个回滚莫队是只减不增的回滚莫队,和之前不一样。这应该是整个题单中最难得题目之一了。

评分:10 分。

小 trick:bitset 套莫队

引言:
这个东西普及和很多了。难度并不算很大。

P3674

bitset 套莫队经典例题。对于刚开始遇到这种题目的人还是很难想出来的。对于 bitset 的掌握能力要求还是很大的。

评分:5 分。

P5355

上一个题的进阶版,多了一个操作,难度还是打了一些。

评分:6 分。

P3674

优化空间的那一步还是比较经典的。

评分:6.5 分。

树上莫队

引言:
这是一个比较恶心的东西,相关的题目也很多。对于树上莫队有两种写法,第一种是树分块,第二种是把树拍平。

P4074

树上莫队+带修莫队,非常恶心,比较考验调题能力和写代码能力。

评分:6 分。

SP10707

也是模板题。

评分:4.5 分。

P4689

就是把 P5268 搬到的树上,难度没有上一题大。

评分:5 分。

P6072

树上莫队+回滚莫队,代码难度还是很大。

评分:6.5 分。

莫队二离

引言:
一个黑科技,现在还不是非常普及。

P4887

莫队二离的板子题,但是难度还是非常大。

评分:7 分。

P5398

第十四分块,莫队二离真正的模板题。不过知道莫队二离之后这个题目还是比较好做的。

评分:8 分。

P7448

莫队二离+二维分块,这应该是这个题单里面最难的一道题之一了。

评分:10 分。


  1. P1494 - [国家集训队] 小 Z 的袜子
  2. P5268 - [SNOI2017] 一个简单的询问
  3. P4396 - [AHOI2013] 作业
  4. P7708 - 「Wdsr-2.7」八云蓝自动机 Ⅰ
  5. P1903 - 【模板】带修莫队 / [国家集训队] 数颜色 / 维护队列
  6. AT_joisc2014_c - 歴史の研究
  7. P5906 - 【模板】回滚莫队&不删除莫队
  8. P8530 - [Ynoi2003] 博丽灵梦
  9. P3674 - 小清新人渣的本愿
  10. P5355 - [Ynoi Easy Round 2017] 由乃的玉米田
  11. P4688 - [Ynoi Easy Round 2016] 掉进兔子洞
  12. P4074 - [WC2013] 糖果公园
  13. SP10707 - COT2 - Count on a tree II
  14. P4689 - [Ynoi Easy Round 2016] 这是我自己的发明
  15. P6072 - 『MdOI R1』Path
  16. P4887 - 【模板】莫队二次离线 / 第十四分块(前体)
  17. P5398 - [Ynoi2018] GOSICK
  18. P7448 - [Ynoi2007] rdiq