【BZOJ 4537】[HNOI2016] 最小公倍数

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4537
神犇题解Ⅰ:http://www.cnblogs.com/clrs97/p/5406018.html
神犇题解Ⅱ:http://blog.csdn.net/heheda_is_an_oier/article/details/51197705

解题报告

考虑只有 ${{\rm{2}}^a}$ 的限制的话
只需要将边和询问排序后依次执行就可以了
具体的话,就是判一判在不在同一个连通块和连通块内的最大值是否符合条件

现在有两个限制,且独立不了的话
那么考虑将 $a$ 分块
边和询问按照 $a$ 所在的块为第一关键字,$b$ 为第二关键字
于是单次询问的加边数量就在 $\sqrt m $ 级别了
于是再搞一个持久化并查集什么的,遇到操作就暴力插入、还原
于是复杂度就是 $O({m^{1.5}}\log n)$ 辣!

2 thoughts to “【BZOJ 4537】[HNOI2016] 最小公倍数”

  1. Very interesting information!Perfect just what I was looking for! “I meant what I said, and I said what I meant. An elephant’s faithful, one hundred percent.” by Dr. Seuss.

  2. Attractive portion of content. I just stumbled upon your web site and in accession capital to say that I acquire in fact enjoyed account your weblog posts. Any way I’ll be subscribing to your feeds or even I success you get entry to constantly fast.

Leave a Reply

Your email address will not be published. Required fields are marked *