Posts match “ 多校 ” tag:

http://acm.hdu.edu.cn/showproblem.php?pid=4630

比较能体现离线威力的一道题。
为了方便使用树状数组维护区间最值,我们从右往左遍历 a 数组,这样查询也要根据 l 从大往小排序。
对于 a[i] 这个数,对它的每个因子 m,我们找一个在 a[i] 右边的,离 a[i] 最近的,且同样有因子 m 的数,其下标为 j,则更新树状数组 j 位置的最值为 m。
为什么找最近的?因为离线查询按照 l 排序后有个天然的包含关系
然后用树状数组查询区间最值就行。

继续阅读