题解：CF1609G A Stroll Around the Matrix

· · 题解

水题一道。

把操作拍差分上，是个后缀加。

走路的过程显然可以贪心（选择较小的一个格子走），因为 a,b 都是凸的。容易用调整法证明任意一条不同于这条路径的路径都不会更优。

记 a' 和 b' 为 a,b 的差分数组，根据贪心过程写出答案的表达式：

ans &= (n+m-1)(a_1+b_1)+\sum_{i=2}^na'_i(n-i+\sum_{j=2}^m [b'_j<a'_i])+\sum_{i=2}^mb'_i(m-i+\sum_{j=2}^n [a'_j\le b'_i]) \\ &= (n+m-1)(a_1+b_1)+\sum_{i=2}^n (a'_i(n-i+\sum_{j=2}^m [b'_j<a'_i])-\sum_{j=2}^m [b'_j\ge a'_i]b'_j)+\sum_{i=2}^m b'_i(n+m-i) \end{aligned}

因为 b' 单调，因此对于每个 i，线段树上二分求出 b'_p<a'_i 的分界点，然后只需要线段树维护后缀加区间求和即可。

https://codeforces.com/contest/1609/submission/345172213。