[ABC438G] Sum of Min

没啥意思的题。

题意其实就是让你求

\[\sum\limits_{i=0}^{n-1}\min(a_i, b_{(pn+i)\bmod m}) \]

其中 \(pn + i \le k - 1\), 即 \(p \in [0, \lfloor\frac{k-i-1}{n}\rfloor] \cap \mathbb{N}\)。

我们有结论：连边 \(i \rightarrow (i + n) \bmod m\)，则会形成 \(\gcd(n, m)\) 个等大的环。

证明：考虑 \(p=0\)，每次 \(p \leftarrow (p + n) \bmod m\)，不断跳直到重新为 \(0\)，加的 \(x\) 总和就是 \(\text{lcm}(n, m)\)，有 \(\frac{\mathrm{lcm(n,m)}}{n}\) 个点连在一起，\(p\) 等于其它同理，所以共有 \(\frac{n}{\frac{\text{lcm}(n,m)}{n}} = \gcd(n, m)\) 个连通块。

而上面那个和其实就是让你从 \(i\) 开始走，走到一个点 \(u\) 则产生 \(\min(a_i, b_u)\) 的贡献，一共走 \(\lfloor\frac{k-i-1}{n}\rfloor\) 步，同时需要算上 \(u = i\)。那么显然可以拆成若干圈和一个前缀，主席树维护一下即可。时间复杂度 \(\mathcal{O}(n \log n)\)。