做题笔记（Feb.）

一月做题笔记

2.1

P4556

复习线段树合并。

---

P4979

复习珂朵莉树。

---

P3605

依旧线段树合并板子。

2.2

P4097

李超线段树板子。

---

P3224

线段树合并板子，但是多了个并查集。（猜猜我为什么以前没用平衡树写过这题）

---

P5494

线段树分裂板子，和合并差不多。

---

CF1009F*

长链剖分板子。

2.3

P5903*

长剖求 K 级祖先的应用板子。

---

CF570D

复习树上启发式合并。

---

CF375D

依旧树上启发式合并。用一个数组记录每个颜色的次数，另一个数组 \(s_i\) 记录有多少种颜色的次数大于 \(i\)。

每次某个颜色增加或减少都是一个一个加减，可以带着 \(s\) 一起更新。

---

CF438D

类似花神游历各国，我们发现每次取模后数都会变为以前的一半以下，所以暴力搞，只会被模 \(\log\) 次。

---

UOJ #228*

看似和花神游历各国一样但是区间加可能会导致如下情况：3 4 3 4 3 4... 开根变成 1 2 1 2 1 2...，然后又全部加回去，直接暴毙。所以我们不考虑全体开根，而是看这一段开根时减少的量是否一样，这样就只用维护最大值、最小值、和，以及一个加多少的 tag。

---

HDU 5634

与花神游历各国同理。

2.4

P14576

双指针。

---

P11596

神秘结论乱搞 \(\text{O}(n)\) 题，发现一些神秘性质后用类似单调栈状物即可。

---

P1712

直接按区间交做扫描线并不好求答案，最好情况应该是双 \(\log\) 的。

换种思路，先按区间长度排序，再双指针一下，确保这个长度范围内的区间能将至少一个点覆盖 \(m\) 次。

---

LOJ #6029

同 UOJ #228，变成区间减。

2.5

QOJ 12565

神秘构造题。

不知道如何发现 \(40\) 大概是这个范围内最大的质数间隙多一点，直接找到比 \(n\) 大的第一个质数，\(ans_{i,j}=p(i-1) + j\)。

---

QOJ 15042

首先要注意到一个性质：Alice 有多少对子你就有多少，因为单牌数量是一样的。

构造方法：如果 Alice 的第一个张和后面能匹配，那你无论如何也阻止不了她，否则你在她的一对数前面随便放上你的一对数，例如：在 2 3... 2 的两个 2 前面分别放一个 1，这样她就得不了分了。至于单牌，按顺序插空即可。

当且仅当 Alice 的第一对牌你吃不掉时她能得一分，否则永远没分。

---

QOJ 16232

选择绝对值在 \([n-x+1,n]\) 中的数，正数从 \(n\) 往下取，负数从 \(-(n-x+1)\) 开始取，把这个区间取完。

假设分为两段，左边是要用作负数的，右边是用作正数的。左右各选 \(k\) 个肯定是左边大，所以我们证一下左边选 \(k+1\) 个肯定比右边选 \(k\) 个大即可。

\[\begin{aligned} &\sum_{i=1}^{k+1}(n-x+i)-\sum_{i=1}^k(n-k+i)\\ =&k^2-(x-1)k+n-x+1\\ =&(k-\sqrt{n}+1)^2+1 > 0 \end{aligned}\]

---

P7453*

矩阵乘法维护线段树的板子题，非常有意思。

换句话说，把维护的值放到一个一行的矩阵里，然后把 \(tag\) 也用一个矩阵表示，每次把用矩阵乘法更新。常常适用于这种维护一堆恶心东西的线段树，但是要注意一下常数优化。这道题实现得好不需要卡常就行。

维护四个东西：三种能量的区间和以及区间长度，区间长度仅用于更新时构造矩阵。\(tag\) 在这里不一一列出，注意初始状态为单位矩阵。

2.6

P4314*

依旧矩阵乘法线段树，但是不是普通的矩乘。因为维护的是历史最大值，所以把原本加乘矩阵乘法中乘法改成加法，加法改成取 \(\max\)，维护当前最值和历史最值即可。注意因为还有区间加和区间推平，所以可以给矩阵加一个空白信息的位置便于修改。

具体矩阵长啥样见代码，注意要用矩阵维护的前提是这种矩阵运算具有结合律和分配律。