想不到吧，一年前的今天我就在这里，一年后的今天我还在这里。
Day 1
-
P1438 无聊的数列。
简单题。
我们注意到差分是再求前缀和是原数组。所以，我们在线段树树状数组上维护差分数组 \(d_i = a_i - a_{i - 1}\)，然后对于每次 \([l, r]\) 进行修改即可。然后在 \(r + 1\) 的位置上再减掉 \(D \times (r - l) + K\) 即可。 -
P2023 [AHOI2009] 维护序列。
板子题。
简单，我们直接把懒标记拆成两个，一个乘法，一个加法。考虑乘法对于加法的优先级，然后随便拆拆就行了。 -
CF438D The Child and Sequence。
势能分析。
我们考虑对于任意一个 \(x > p\)，一定有 \(x \equiv y \pmod p\)，且 \(0 \le y \le p - 1\)，则定有 \(y \times 2 \le x\)。
所以，每一个 \(x\) 至多经历 \(\log x\) 次数就会变成 \(0\)。
我们考虑势能分析，单点至多赋值 \(m\) 次，所以总的时间复杂度就是 \(O((n + m) \log V)\)。 -
CF61E Enemy is weak。
简单题。
直接考虑中间的点，考虑前面多少个严格大于 \(a_i\)，后面多少个严格小于 \(a_i\)，再乘在一起再相加即可。 -
CF935F Fafa and Array。
我们考虑，对于我们把 \(pos\) 这个位置的值加上 \(x\)，会产生的贡献是 \(2 \times (x - \max(-d_{p - 1}, 0) - \max(d_p, 0))\)。下面的思路比较显然了，我们令 \(g_p = \max(-d_{p - 1}, 0) + \max(d_p, 0)\)，我们使用线段树维护这个区间的 \(\min\)，然后对于 corne cases 直接处理即可。 -
CF1527E Partition Game。
考虑DP。
设 \(f_{i, j}\) 表示前 \(i\) 个数字恰好分成 \(j\) 组，那么我们轻松列出转移方程：
\(f_{i, j} = \min f_{k - 1, j - 1} + w_{k, j}\)
其中，\(w_{i, j}\) 定义为 \([a_i, a_{i + 1}, ..., a_{j - 1}, a_j]\) 的 \(cost\) 值。
接下来考虑如何计算 \(w\) 值。很明显，如果 \([i, j - 1]\) 中存在一个 \(a_k = a_j\)，那么 \(w_{i, j} = w_{i, j - 1} + j - lst_{a_j}\)，其中 \(lst_{a_j}\) 表示 \(a_j\) 最后一次出现的位置；否则，\(w_{i, j} = w_{i, j - 1}\)。这样我们得到了一个复杂度为 \(O(n^2k)\) 的做法。
考虑线段树优化。我们令线段树的 \(st_k = f_k + w_{k + 1, i}\)，我们可以发现，如果 \(k + 1 \le lst_i\) 的话，则 \(a_i\) 并非首次出现，所以我们这时候可以统计上代价。所以，我们对于区间在 \([1, lst_{a_i}]\) 中的每一个元素加上代价为 \(i + 1 - lst_{a_i}\) 即可。复杂度为 \(O(nk\log n)\)。 -
CF833B The Bakery。
我们容易发现，这个题和上面那个题的解法大致一致。
我们状态设的一样，然后我们考虑，对于 \(lst_i \le p\) 的所有位置，这个的数字个数会加上一，所以我们只需要改一下上面的修改的地方就可以了。还是非常相似的。 -
CF813E Army Creation。
我们使用瞪眼大法，令 \(bad_i\) 表示从 \(i\) 向前数 \(k\) 个的位置。特别地，如果没有这么多，那么我们令 \(bad_i = 0\)。
接下来，我们直观的发现，我们只需要令在区间 \([l, r]\) 之间的所有同一个值的元素的前 \(k\) 个的权值为 \(1\)，剩下的是 \(0\)。注意到，这个条件等价于 \(bad_i < l\)，所以我们的统计问题就是在 \([l, r]\) 之间 \(bad_i < l\) 的个数。考虑主席树优化即可。 -
CF893F Subtree Minimum Query。
我们考虑直接做的话不会很好做，所以我们考虑再 DFS序 上面做。
我们考虑，对于所有在 \(x\) 的子树中，定存在 \(dfn_x \le dfn_y \le dfn_x + size_x - 1\)，而且我们要找出 \(dep_y \le dep_x + k\)。所以，我们用 dfn 建立可持久化线段树，然后支持区间查询即可。