做题记录（Jan.）

12 月做题记录

1.2

CF1638E

新年第一题。发现第一种操作和珂朵莉树的 assign 很像，考虑用珂朵莉树维护。

对于第二种操作，可以打懒标记，表示某种颜色加了多少。

那么在做第一种操作时，我们就需要把原来的懒标记给处理了再变色，并且变色后还需要减去这个颜色的懒标记以保证答案正确。

处理懒标记涉及区间加，第三个操作是单点查，所以可以树状数组维护。

---

P9320

和上面一道差不多，但是多了一个 LCA。

---

CF981G

用 \(n\) 珂朵莉树维护每个可重集中有没有 \(i\)，每次 assign 时对于每个段，若值是 \(0\) 就在线段树上 \(+1\)，否则 \(\times 2\)，然后把 assign 的区间都赋值成 \(1\)。

1.4

P8435*

点双板子。

1.9

CF487E*

被我写的弱智重剖硬控了一周。

先用 tarjan 缩成圆方树，然后每个圆点记录自己的值，方点记录在树上自己儿子的值的最小值。

剩下的全都是重剖，查询时如果 LCA 是方点，额外和它的父亲取个最小值。

全当复习重剖了。

1.10

• 莫队

P1494*

普通莫队板子。

---

P1903*

带修莫队板子。

1.12

P4074*

树上（带修）莫队板子。

---

P5906*

回滚莫队板子。

1.13

P14420 & AT_joisc2014_c

又是回滚莫队板子。

---

P3901

可以莫队做，但是不需要。

记录每个点前面最靠近的两个相同数的第一个最大是多少。用 \(maxn\) 记。则询问 \([x,y]\)，如果 \(maxn_y\) 小于 \(x\) 即可。

1.15

P2709

真正的普通莫队板子。

---

P4396*

看起来很像莫队或主席树，但是多了一个值域限制。那么我们容易想到莫队的时候用一个数据结构来维护和查询。树状数组带 \(\log\) 要卡常。通过观察我们发现对于这个数据结构的修改有 \(n\sqrt{n}\) 次而查询只有 \(n\) 次，所以我们可以用单点修改时 \(\text O(1)\)，区间查询时 \(\text O(\sqrt{n})\) 的值域分块。

这还是我第一次打值域分块……不过好消息是一遍过了（就是不知道自己打的是什么马蜂的分块，感觉与众不同）。

1.16

P5268

看题解吧，我不会推式子。

1.19

P3803*

FFT 板子，但是还没学会原理。

---

P1919

还是 FFT 板子。

1.22

CF993E*

好像是 FFT 的一个常用技巧，可以学习学习题解。

1.24

P3723

先把加上偏移量的平方拆一下，然后就会发现只用最大化一个东西，这个东西可以用上面那个技巧搞一搞，就可以 FFT 了。

二月做题笔记