rt

蒟蒻只想到：

1. 对每个维度计算每个点在这个维度（最早的）出界的步数，然后再对每个点统计答案；直接实现复杂度是 $\Theta(n+k\prod w_i\log n+k\prod w_i)$（里面的 $\log$ 是维护前缀和用并在线段树上二分找出界步数；实际实现时还有各种讨论）
2. 考虑计算维度 $k$ 时，其它维度的坐标并不会影响这个维度的答案；于是考虑计算出 step[k][x] 表示在维度 $k$ 的坐标为 $x$ 时，该维度出界的步数，这样这部分就优化到了 $\Theta(\sum w_i\log n)$。接着想到只有最小的出界步数才会产生贡献。于是考虑这样一种计算贡献的方式：设 $l_i$ 表示 step[i] “剩余” 的元素个数（初始即为 $w_i$）；从所有 step[.][.] 中找出值最小的元素 step[k][x]，其可以产生 $\prod\limits_{i \not=k} l_i$ 的贡献，然后再 “删掉” step[k][x]；如此重复直到有 step[i] 的元素个数为 $0$；这一部分应该可以在 $\Theta(\sum w_i\log {\sum w_i})$ 内实现。于是最后的复杂度为 $\Theta(n+\sum w_i\log n+\sum w_i\log {\sum w_i})$

然而仔细算了下 $1.$ 和 $2.$ 的分数都是一样的...都过不了后面两个包（

另外还听说可以拿多项式做什么（link），不过我不太了解qaq