7
这个区忘了 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∣))，证明略
有帮助，赞一个