https://www.luogu.com.cn/article/cp972354 这篇文章综合了几乎所有本题可用的 ST 算法优化，重新理解 ST 算法，最后给出图形解释深入理解本题各种 ST 写法的原理。 题解给出的终极写法导向本题最优解，时间复杂度小常数 $O(ab\log n)$（在算法竞赛的数据上限下，即使加…

在文章《P2216 [HAOI2007] 理想的正方形 题解》发表评论：

噶人们手写代码是个好习惯不要随便 copy

在讨论《建议添加标签：ST 表》回复：

最优解是 ST 算法。

[评测记录](https://www.luogu.com.cn/record/201008163) ```cpp #include using namespace std; int n; char str[1000002]; int ans = 0; int x[1000001], y[1000001], z[1000…

$\text{权重}\times\text{数字}$ 这一步中，即使保证 $\text{权重}$ 在 $[0, 10007)$ 范围内，因为 $\text{数字}$ 最大可达 $10^6$，直接乘会爆 $32$ 位整数。

计算 $b-w*w$ 时，$w*w$ 会爆 32 位整数。 如果你直接框选 $w$ 的取值范围避免判断 $\frac{m}{n}$ 是否为正数，需要注意分类讨论两种不同的范围，同时边界必须严格正确，注意各种取整的正确应用。 判断 $\frac{m}{n}$ 是否为正数，以下方法在本题中是不行的： - $m*n>0$ 在…

示例： ```lua --[[ print("Debug print t:") for k, v in ipairs(t) do print(string.format("t[%s]=%s",tostring(k),tostring(v))) end print("Debug print t end.") --]] -…

最后处理 $>\sqrt{a}$ 的质因数时，仍要处理 $b$（应该只有我有这个错误吧）。

在讨论《添加标签&难度》回复：

这题虽然可以`离散化`转移 DP，但大部分 AC 代码都是用的 STL 映射表，因此不加 `离散化`

添加标签 `最大公约数 gcd`, `动态规划 DP`, `哈希表`。 洛谷等级难度 3~4。 - 难度 3`普及/提高-` - 难度 4`普及+/提高`

在讨论《喜欢卡哈希模数的出题入你们好啊》回复：

算法竞赛故意卡哈希取模没啥意义，一般只能卡算法竞赛中总所周知的大质数，测试点数目有限对特定模数能卡的点也不多，而且真开大的话选手直接随机生成大质数……

在讨论《申请添加 hack，撤下题解，添加题解》回复：

@[liuzhuoran141516](luogu://user/1351155) 不是哥们代码就 $6$ 行注释，哪里来什么无意义注释？再说注释有没有用因人而异，个人觉得没用不代表对其他人没用。评价他人的题解起码有别人一半的推荐题解吧

在讨论《申请添加 hack，撤下题解，添加题解》回复：

@[liuzhuoran141516](luogu://user/1351155) 不是到底什么问题啊？我也是照着[洛谷主题库题解规范（2023 试行版）](https://help.luogu.com.cn/rules/academic/solution-standard)写了几篇通过的题解的，你这个意义不明

[关于 Hack 数据](https://www.luogu.com.cn/discuss/1030470) 看了一遍题解区的非图论做法，只是讲了如何区间 $-1$，而没有讲正确性，因此申请撤下部分题解，添加[题解](https://www.luogu.com.cn/article/h4hqstbc)。

看了一遍题解区，发现并没有详细讲明为什么区间减一正确的题解，特发题解讲解。 ## 题目简析 给定一个长度为 $n\le10000$ 的整数数组 $A$，给出一个最大值 $A_i=h$（由样例答案可知最大值位置不唯一），接下来给定 $R$ 个关系 $\langle a,b\rangle(a\not=b)$，对 $A$ 有…

运行以下代码即可。 ```cpp #include using namespace std; const int n = 10000; const int i = 10000; const int h = 1000000; const int R = n-1; int main(){ freopen("P2879.in…

在讨论《请求添加 hack，题解区几乎沦陷！》回复：

@[nr0728](luogu://user/682739) 修正：题解 #7 的链接应为 https://www.luogu.com.cn/article/kmfiota8 评测结果表明题目中的代码根本跑不了

在讨论《请求添加 hack，题解区几乎沦陷！》回复：

@[nr0728](luogu://user/682739) 键盘误，链接写混了

## hack 数据 ### hack 输入 ```plain 1 1 1 6 1000000000 1 1 1 1 1 1 1000000000 1 1 1 1 1 1 1000000000 1 1 1 1 1 1 1000000000 1 1 1 1 1 1 0 1 1 1 1 1 1 0 1 1 1 1 1 1…

> 很多题解仅仅把这道题的倍增优化 DP 当成类似树上倍增 LCA 的简单倍增。 > > 但实际上直观定义出来的 DP 状态在某些方面上没有**最优子结构**性质（下文会展开叙述），并不适合倍增，而是需要进行一些特殊转化才能用倍增优化，本题解用**等效法**来构造合适的 DP 状态。 ## 题目分析 ### 形式化题意…

添加标签 `动态规划 DP `, `动态规划优化`, `倍增`。

在讨论《警示后人》回复：

@[candy0014](luogu://user/481803) 操作 1 的操作数写反了

倍增跳跃的过程中，一定要特别注意特殊情况的处理，多连几条边也不少连，有以下几种可能出错的特殊情况： 1. $u=v$，这时候必须用原图上的点 $u,v$ 连边。 2. $u, v$ 同步深度后，如果 $u=v$，直接退出，不要在 $u, v$ 的倍增虚拟节点上连边。 3. $u, v$ 同步深度后，如果 LCA 就是它…

rt

添加 `排序`, `双指针,two-pointer`, `st表`, `并查集` @[Maxmilite](luogu://user/274993) @[minstdfx](luogu://user/100250) @[_bzy](luogu://user/213388)

## 题目分析 给定一个长度为 $N(N\le10^6)$，值域为 $[1, 10^6]$ 的整数数列 $Num_1, Num_2, Num_3, \dots, Num_N$。 定义区间数 $\text{cnt}(x)$ 与分数 $\text{score}(x)$： > 将 $Num$ 中所有 $\le x$ 的数标记…

1. 计算或比较新权重 $=\frac{score}{num}$ 时，记得强制转为浮点数（比较法的可以转为乘法比较）。 2. 原始得分的最大值可达到 $(10^6)^2=10^{12}$，超出 $\text{int32}$ 的范围。 3. 计算 $[l, r]$ 时可能发生越界，分析如下： > $lastans$ 的最…

在讨论《最优询问下究极压长度191字节（违规紫衫）》回复：

补充：这题可以不刷缓冲区，可以用 `printf("%d\n",n)` 询问，少用两个 `std::`，去掉 `using namespace std;`，由于变量都是全局的所以 lambda 不要引用捕获，`#include` 可换成 `#import`，新代码 `176B+1换行`。 新代码： ```cpp #im…

在讨论《最优询问下究极压长度191字节（违规紫衫）》回复：

@[zjr2014](luogu://user/1050483) 缓冲区还是要显式刷新的。

有点类似题解的性质，违规紫衫。 [评测结果](https://www.luogu.com.cn/record/194738220)，最多询问次数为 $30$，是最优询问。 最终代码 ```cpp #include using namespace std;int a,*z,n,r;int main(){lower_bou…