RainAir
My OI Blog
RainAir
「NOI2002」银河英雄传说

题意描述

有 300,000 个元素,每种元素初始时以单独队列存在,支持下面两种操作:

1.合并两个队列,即将x元素所在队列首部接至y元素所在队列的尾部。
2.查询两个元素x,y是否在同一队列,如果是,则求两元素的间隔元素的数量

操作 500,000 次

链接

洛谷

题解

我们可以显而易见看出这是一道并查集的题目,在这里我们要使用一种叫做带权并查集的东西。
对于带权并查集,我们需要维护一个权值$ dist[i] $表示$ i $到$ f[i] $的距离。
然后就套用并查集模版,注意路径压缩和合并时候顺便处理一下$ dist[i] $即可。

代码

赞赏
知识共享许可协议
本文链接: https://blog.aor.sd.cn/archives/137
如文中无特殊声明,本文采用 CC BY-NC-SA 4.0 进行许可,转载请说明出处!
希望 CSP 不要翻车,希望省选不要翻车
https://secure.gravatar.com/avatar/97c17c68a1e55e11bb5558bc0f10cc0d?s=256&d=mm&r=g

RainAir

文章作者

一个OIer。

发表评论

textsms
account_circle
email

RainAir

「NOI2002」银河英雄传说
题意描述 有 300,000 个元素,每种元素初始时以单独队列存在,支持下面两种操作: 1.合并两个队列,即将x元素所在队列首部接至y元素所在队列的尾部。 2.查询两个元素x,y是否在同一队…
扫描二维码继续阅读
2018-02-20
标签
近期评论