ABC366 题解

标签：frac 前缀 题解 纵坐标 ABC366 DP

D - Cuboid Sum Query

三维前缀和。不过有一维范围小，可以暴力然后二位前缀和。

E - Manhattan Multifocal Ellipse

横纵坐标的距离是独立的。
扫描线扫横坐标，维护每个可行点的纵坐标的距离和，查询就是 \(\le x\) 的数的个数。
可以通过桶做到线性。

F - Maximum Composition

Exchange Arguments.

首先我们想的是如果能确定选的顺序，就能一遍 DP 快速求出答案了。
考虑贪心地给他确定一个顺序。
考虑对于 \(x\) 和 \(x + 1\)：
原本的贡献为：

\[B_{x + 1} A_{x} + B_{x} \]

交换后的贡献为：

\[B_{x} A_{x + 1} + B_{x + 1} \]

如果想要交换更优，那么要有：

\[B_{x} A_{x + 1} + B_{x + 1} - B_{x + 1} A_x - B_{x} = B_{x} (A_{x + 1} - 1) - B_{x + 1} (A_{x} - 1) > 0 \]

也即：

\[\frac{A_{x + 1} - 1}{B_{x + 1}} > \frac{A_{x} - 1}{B_{x}} \]

验证一下：强完全性 和 传递性 肯定是都有的，所以直接排序就是对的。
按这个比较排序即可，之后的 DP 是简单的，就是什么 \(f_{i, j}\) 表示前 \(i\) 个函数复合了 \(j\) 个的最大值。

时间复杂度 \(O(n (k + \log n))\)。

G - XOR Neighbors

直接高消。感觉这个 G 挺搞笑的。

标签：frac,前缀,题解,纵坐标,ABC366,DP
From： https://www.cnblogs.com/definieren/p/18353652