10
这个区忘了 ST 表，导致 S 初赛被周飞，所以只有 J 打了。
标题何意味.
由于和上一篇训练目的不同，所以单开。
9.24
拜谢 FM 大佬，开始刷题单棍母和棍母
P7909
时候不早了，随便挑个橙玩玩。
因为要找到最大的 kmod nk \mod nkmodn，如果 l,rl,rl,r 除以 nnn 的商下取整相等，则在满足 L≤k≤RL \le k \le RL≤k≤R 的情况下 kkk 越大越好，于是我们取 k=Rk=Rk=R。否则，kmod nk \mod nkmodn 最大值明显为 n−1n-1n−1，直接输出 n−1n-1n−1 即可。
代码
复杂度分析
略
9.25
中秋快乐各位。
13 天假期必须好好补一补 whk 了，也（打算）报了洛谷的课程。但先玩几天（
在酒店看一会 J/S 的题目讲解
9.26
是谁写了一沙滩的毕导。
晚上帮 cchu 调代码，顺便讲一下吧。题目是今晚 ABC 的 D。
这种类型的题目 ABC 似乎出烂了，AtCoder 你只是怕了。
显然 lazy tag 优化，直接线性创飞了。
然后你会收到 AC18，WA13 的好成绩。
下面给一组 hack：
相信大家都知道错在哪了，如果直接去判断当前格子的染色状态会很麻烦，复杂度也会炸。也就是说正着维护很难。
触发关键词了。
没错，正难则反。我们反着去处理查询，每次只要找到这个格子最后一次的有效染色即可。
代码
略
复杂度分析
略
9.28
florr 玩破防了，老实滚回来写题。
P1182
唔，一个简单的二分答案，所以我们确定三个点：
1. check 函数
2. 二分边界
3. 二分内容
二分内容不难想，题目要求我们求最小最大值，所以我们二分这个值。边界也比较简单，显然当我分为 n−1n-1n−1 段时答案最小，为 max(a1,...,an)\max(a_1,...,a_n)max(a1 ,...,an )；不分段时最大，为 ∑i=1nai\sum_{i=1}^{n} a_i∑i=1n ai ，那么边界就没问题了。
来看 check 函数。我们要在保证答案为 midmidmid 的情况下，所分段数不超过 mmm。考虑 O(n)\mathcal{O}(n)O(n) 求分段数，若当前这一段大小超过 midmidmid，则划分新的一段。由于我们需要 O(1)\mathcal{O}(1)O(1) 维护静态区间和，所以使用前缀和数组。
那就做完了。
代码：
复杂度分析
比较简单的分析，二分复杂度 O(logk)\mathcal{O}(\log k)O(logk)，check 函数复杂度 O(n)\mathcal{O}(n)O(n)，总复杂度 O(nlogk)\mathcal{O}(n \log k)O(nlogk)。其中 kkk 为 ∑i=1nai−max(a1,...,an)\sum_{i=1}^{n} a_i -\max(a_1,...,a_n)∑i=1n ai −max(a1 ,...,an )。
P14247
好神奇的题。
乍一看感觉条件三很难，尝试找规律。
看了一眼样例，没有给我们不合法的情况，猜测都是可以的。
从 n=2n=2n=2 开始看，发现随便填都符合条件，当时推到这就开智了。
显然我们构造的这个矩阵中只要包含一个 2×22\times 22×2 的由 1,2,3,41,2,3,41,2,3,4 组成的子矩阵即可满足条件三。
发现条件 333 要满足“恰有”，看看怎么放可以不出现第二个如上的子矩阵。我们假设 n=3n=3n=3，在上述条件下，我们可以在右侧与下侧全部填 555，右下角填 666，构造出来的矩阵是这样的：
那怎么往下扩展呢，看看 n=4n=4n=4 的情况，按照上述方法构造，矩阵如下：
发现，若 (n−1)×(n−1)(n-1) \times (n-1)(n−1)×(n−1) 是一个合法的构造，考虑在其右，下侧最后一列（排）放入 2x−12x-12x−1，最右下角放 2x2x2x。不管怎么圈，除了最左上角的子矩阵外，总是有且只有两个数重复。这样就满足了“恰有”这个条件，进而满足了所有条件。
代码
略
复杂度分析
显然为 O(n2)\mathcal{O}(n^2)O(n2)
10.1
P17288
高速上写的，脑子不清醒写了个石山。
直接模拟即可，思路不讲诗人都会吧。
代码
复杂度
O(max(∣a∣,∣n∣))\mathcal{O}(\max(|a|,|n|))O(max(∣a∣,∣n∣))，证明略
10.5
P10722
看看怎么维护一个节点的翻转次数。
思考一下节点翻转的情况。思考发现这个节点的实际翻转数等于他父节点的翻转数加上他本身的翻转数。我们发现需要维护父节点翻转数。
令当前节点为 xxx，fa(x)fa(x)fa(x) 与 f(x)f(x)f(x) 分别为求父节点与求自身翻转次数。则当前节点翻转次数为 f(x)+f(fa(x))f(x)+f(fa(x))f(x)+f(fa(x))。对于 fa(x)fa(x)fa(x)，其翻转次数为 f(fa(x))+f(fa(fa(x)))f(fa(x))+f(fa(fa(x)))f(fa(x))+f(fa(fa(x)))。以此类推。我们发现需要从根节点向下一步一步维护翻转次数，考虑 dfs。
用三个数组 dp,func,fadp,func,fadp,func,fa 维护。funcfuncfunc 为当前节点作为根节点的翻转次数。则每次搜索转移为 dpi=funci+dpfaidp_i=func_i+dp_{fa_i}dpi =funci +dpfai 。那就做完了。
代码
略
时间复杂度
O(n)\mathcal{O}(n)O(n)，证明略
有帮助，赞一个