如何将杂题2转化为？

\(\text{QOJ 5458. Shortest Path Query}\) 首先想到每次询问在 \(\text{DAG}\) 上 \(dp\) 一次求最短路 这是没法优化的 考虑预处理到 \(i\) 可能经过的黑白边数 即预处理 \(f_{i,j}\) 表示经过 \(j\) 条黑边到 \(i\) 所需经过的最少白边数量 可以视为点对 \((j,f_j)\) 那么询问就是找到一个点 \((x,y)\) 使 \(ax+by\) 最小 这个是很好做的，维护下凸包，询问在凸包上二分即可 而观察一开始的 \(dp\) 转移，发现只转移下凸包上的点就足够了，不在凸包上的点不优，转移出去也不优 这个复杂度是怎样的呢？题解中说对于一个 \(i\)，它至多有 \(O(n^{\frac 2 3})\) 个状态在凸包上，即凸包上点数有保障，那么总复杂度就是 \(O(mn^{\frac 2 3}+q \log n^{\frac 2 3})\) 提交记录 \(\text{[CF1634F] Fibonacci Additions}\) 判断两数组是否相等可以对应位相减，判断是否全为 \(0\) 即可 考虑怎样描述一次区间操作，可以快速判断是否全为 \(0\) ？ 区间加斐波那契数列不好用数据结构打标记，另寻它路 注意到斐波那契数列有很好的递推形式，其差分 \(D_i=f_i-f_{i-1}-f_{i-2}\) 后为 \(f_1,f_2-f_1,0,0,...\) 如果 \(A,B\) 的差数组也如此差分，那么照 \(s_i=D_i+s_{i-1}+s_{i-2}\) 这样做前缀和后便可复原 此时不难发现区间加斐波那契数列就变成 \(D_l\leftarrow D_l+f_1,D_{r+1}\leftarrow D_{r+1}-f_{r-l+2},D_{r+2}\leftarrow D_{r+2}-f_{r-l+1}\) \(O(1)\) 修改，记录 \(0\) 的数量即可判相等 似乎许多 \(m\) 阶常系数递推数列都可以这样做 \(O(m)\) 提交记录 \(\text{[ABC270Ex] add 1}\) 计数器 \(i\) 均大于等于 \(A_i\) 这个终止条件不好体现，如果每个计数器从 \(A_i\) 开始，\(+1\) 边 \(-1\)，那么只需关心最大值是否小于等于 \(0\) 能否只将最大值纳入 \(dp\) 状态？这个足够的，考虑最大值 \(mx\)，找到 \(r\) 使得 \(A_r < mx \le A_{r+1}\) 操作 \(1\) 到 \(r\)，最大值变为 \(mx-1\)；操作 \(r+1\) 到 \(n\)，最大值相应变为 \(A_{r+1}\) 到 \(A_n\)。也就是只需要最大值就可以更新 \(dp\) 状态 那么由此写出转移 \(f_k=\frac 1 n \sum_{i=r+1}^n f_{a_i} + \frac r n f_{k-1},k\in (A_r,A_{r+1}]\) 移项，\(f_{k-1}=\frac n r f_k - \frac 1 r \sum_{i=r+1}^nf_{a_i}-\frac n r\) 这样就有顺序了，但 \(f_{a_n}\) 才是要求的呀，只知道 \(f_0=0\) 所以设 \(f_{a_n}=x\) 递推到 \(f_0\) 解出 \(x\) 即可 转移写个矩阵就够了 提交记录 \(\text{P4062 [Code+#1]Yazid}\) 的新生舞会 发现一种暴力做法 \(O(n\log^3n)\)，比一些人写的 \(O(n\log n)\) 还快（事实上三 \(\log\) 能过 \(5e5\) 已经很震撼了） 数区间不难想到扫描线或者分治 但考察众数较为困难，所以从暴力开始 不难想到暴力枚举区间 \(O(n^2)\)，而如何判断区间是否合法可以 \(O(n)\)，因为绝对众数很厉害，枚举区间时顺势扫下，相异两数同时删掉，总复杂度 \(O(n^2)\) 类似上面相消思想，枚举绝对众数，将其赋为 \(1\)，其余赋为 \(-1\)，区间合法只需区间和为正 于是 \(O(n^2\log n)\) 成功负优化。