Posts match “ 离线 ” tag:

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=509&page=show_problem&problem=4225

思路:离线+逆序操作。逆序后删边变连边,用并查集判连通性即可。Q操作用名次树解决,C操作拆为删除和插入两个操作。
顺便附上我的Treap+名次树模板。

继续阅读

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

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

继续阅读

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

首先离线,按 r 从小往大排序。

由不等式 可知,集合的个数越少越好。那么这道题的关键就在于如何「合并」集合。

为了说明的方便,举个例子:

设 ID 数组为 1,3,2,5,4,我们从左往右遍历,每读到一个数,树状数组当前位置就 +1,表示新增一个集合。

然后试着合并,看当前位置 i 前面有没有 a[i]-1 和 a[i]+1,有的话树状数组 pos[a[i]-1] 和 pos[a[i]+1] 就 -1,表示合并集合。

注意,遍历到最后一个数 4 的时候,我们把 3 和 5 所在位置各 -1(合并集合),但是先前遍历 2 的时候已经把 3 所在位置 -1 了,这对结果是没有影响的,因为查询的时候,3 会与 2 相互抵消。

继续阅读