这题洛谷的数据太…水,克鲁斯卡尔重构树不连通都可水过。

  • 3545: [ONTAK2010]Peaks
  • 3551: [ONTAK2010]Peaks加强版

在线算法:克鲁斯卡尔重构树套主席树。

在克鲁斯卡尔重构树上维护 DFS 序(或树链剖分)再套上主席树,维护第 $k$ 大。

当然非加强版由于你是重构树(被针对了)可能要大力卡常。比如加个 fread 以及离散化一下什么的。

这道黑题为什么那么水 QAQ
这道题在 BZOJ 上为什么又又又又又是权限题

本题求区间众数,强制在线。

对于每次查询,必定可以分为整块的和非整块的,我们先预处理出第 $i$ 块到第 $j$ 块的众数( $max[i][j]$ )和某个数 $i$ 在前 $j$ 个块内的前缀和( $sum[i][j]$ )。对于非整块的部分 $O(\sqrt n)$ 暴力加到桶里,加上整块中的个数判断能否更新答案。然后判断 $l$ 与 $r$ 之间的块的众数是否能否更新答案。

预处理的话 $max$ 和 $sum$ 数组全都暴力扫一遍更新,时间复杂度 $O(n \sqrt n)$,详见代码。

时间复杂度:$O(n \sqrt n + m \sqrt m)$

洛谷4768 - [NOI2018]归程

真是纳闷,为什么这题在 BZOJ 上是权限题???

首先你需要了解一下 这种算法,然后你在重构树上树形 DP 处理出子树中距离的最小值,最后对于每次询问倍增找出最高点回答即可。

过程就不详细说啦,相信在坐的各位大佬早就会啦。。。

不过也有 sqq 这种巨佬写了可持久化并查集 AC 了的 QAQ ,下次写写。

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×