ARC133B

FiraCode · 2023-12-01 19:41:21 · 题解

思路：

发现是排列，于是考虑直接枚举 a_i 的倍数对应 b 序列中哪个数，显然的调和级数时间复杂度 \mathcal{O(n \log n)}。

于是对于每个数对 (i,j)，其实就是选出尽可能多的点使得 i 和 j 都严格单调递增，那么可以考虑将其中一维排序（满足一维的单调状态），然后对另一维再去用经典的贪心或权值树状数组做即可。