CF1575I Illusions of the Desert
看这个边权这么复杂，猜测其必然有一些性质。对 \(a_u,a_v\) 的正负分讨易得 \(\max(|a_u+a_v|,|a_u-a_v|)=|a_u|+|a_v|\)，树剖树状数组单点修改链求和即可。
ABC177F I hate Shortest Path Problem
考虑 dp，设 \(f_{i,j}\) 表示到达第 \(i\) 行第 \(j\) 列的最短路。
因为到了某一行后再向右走一定不会更优，所以每次更新后的最短路一定是向下走得到的，所以规定 \(f_{i,j}\) 必须向下走，同时对于右没用的点我们先不管他。
那么：
\(f_{i,r+1}=\min_{l \le i \le r} f_j-j+r+2\)
\(f_{i,j}=f_{i-1,j}+1,j \notin [l,r]\)
\(f_{i,j}=+\infty ,j \in [l,r]\)
线段树维护 \(f_{i}\) 即可，变成正无穷可以加上一个大数。
P8446 虹色的北斗七星
确定了 \(\max-\min\)，那么区间显然不会再扩大了，所以 \(\max\) 和 \(\min\) 应该是区间的两端。
那这就是简单题了，求
\[\max(\max_{1 \le i \le n} \max_{j \le i}a_i-a_j-i+j-1,\max_{1 \le i\le n}\max_{j \ge i}a_i-a_j-j+i-1) \]即可。为啥这样保证了 \(\max \ge \min\) 呢？其实是不保证的，但是 \(\max-\min<0\) 显然不优啊。
标签：le,min,2024.9,短路,笔记,ge,max From： https://www.cnblogs.com/aCssen/p/18432235