首先注意到一个关键性质 \(b_i \geq 1\)，这就意味着当我们花 \(p\) 的代价解锁了 \(b_i\) 最小的后，仅凭接下来的“连锁反应”就能解锁全部的点。注意到我们“连锁反应”的一定是按 \(b_i\) 从小到大排序后的一段前缀（因为越往后连锁代价越昂贵），找到转折点后面每个点分别花 \(p\) 的代价解锁即可。
时间复杂度 \(O(n \log n)\)。
我们考虑计算每一个点最大值的贡献次数。假设说所有 \(a_i\) 互不相同，那么如果说 \(a_i\) 想要贡献，就一定要选择至少一个 \(i\) 的因子 \(j\) 对应的 \(a_j\)，并且还要保证不存在一个位置 \(k\)，满足 \(k\) 是 \(j\) 的倍数且 \(a_k \geq a_i\)。实际上我们只需要从大到小枚举所有数，先看一下有多少 \(i\) 的因子 \(j\) 对应的数未被删除，计算完当前数 \(i\) 后删掉所有 \(i\) 的因子 \(j\) 对应位置的数即可。对于 \(a_i=a_j\) 的情况，只需先计算位置更靠后数即可。
时间复杂度 \(O(n \log n)\)。
我们考虑建立图论模型。对于点对 \((i,a_i)\) 就从 \(i\) 向 \(a_i\) 连一条边，表示 \(i\) 想要留存在集合内的话必须将 \(a_i\) 删去（注意到这样建出的图必然是基环内向树森林）。如果我们设留在集合内为黑色，删去为白色，那么我们可以注意到一个染色方案合法的充要条件是不存在一个黑点指向另一个黑点，且不存在一个白点满足没有黑点指向它。于是我们只需要构造一组合法的方案即可。
注意到对于树的部分答案是唯一的（由于叶子只能为黑点，可以逐层向上确定），对于环则只有两种确定答案的方式。强制枚举环上每个点的颜色暴力检验合法性即可。
时间复杂度 \(O(n)\)。
首先第二个条件可以转化为不能存在两个点 \(i,j\)（\(a_i=a_j\) 且不存在 \(i<k<j\) 满足 \(a_k=a_i\)）染了相同的颜色。对于题目要求我们计数的东西（蓝色字典序小于红色字典序），不难发现答案就是两者所选序列不相同的方案数除以 \(2\) 的结果（考虑每个合法的方案交换颜色后必然唯一对应一组不合法的方案）。所以我们用总方案数减去两者所选序列完全相同的方案书即可。
首先我们只要存在一组相等的方案，一定是可以通过贪心简单构造出来的。具体来讲就是能往对于第一次出现的权值，直接染成蓝色，接下来交替染色。如果这样都不能相等就说明不可能相等了。
在这个基础上考虑如何调整出其他的方案，注意到我们之前钦定每种权值都优先染蓝色。所以如果想要构造出新方案，只要让某些权值有限染红色即可。但我们当然不能随便决策，因为可以发现一些颜色是绑定的。具体来讲如果说一种权值之前出现过奇数次，那么它的决策就会和当前权值的决策绑定。对于这种“绑定”的形式显然可以使用并查集维护。对于维护以哪些点为根的连通块存在出现奇数次权值的问题，使用 set 进行维护即可。
时间复杂度 \(O(n \log n)\)。
标签：902,based,黑点,复杂度,我们,即可,权值,Round From： https://www.cnblogs.com/Hypercube07/p/17750510.html