CF840D

题目链接

注意到一个很有趣的事情是，一个数如果在长度为 \(l\) 的区间中出现次数严格大于 \(\frac{l}{k}\) 次，那我从这个区间中期望随机 \(k\) 次就能随到它。

所以我们对于每个询问，都先随机 \(B\) 次，把随机到的数挂进一个 vector，我们对这里面的数进行 check ，把满足条件的数取个最小值即可。

现在问题在于快速 check。当然可以主席树或者挂若干个 vector 然后在里面 lower_bound，但是这样复杂度是 \(O(qB\log n)\) 的，我们希望有一些更为纯真的做法。

莫队，把 vector 挂下来，然后对询问跑莫队，维护当前区间内数字内出现次数即可 \(O(1)\) check。时间复杂度 \(O(n\sqrt{q}+qB)\)。

CF364D

题目链接

很有趣的题目，但是忘了我啥时候做的。

考虑最终答案有啥性质，他一定是超过 \(\frac{n}{2}\) 个数的因子。这意味着我如果随机选一个数字 \(x\)，我将其和其他数字取个 gcd 并把得到的 gcd 扔到一个桶里计数，然后对桶里的东西做 Dirichlet 后缀和，答案就有 \(\frac{1}{2}\) 的几率是出现次数大于 \(\frac{n}{2}\) 的数中的最大值。

那我多随几次就做完了，设随机次数为 \(B\)，则错误率为 \(\frac{1}{2^B}\)。时间复杂度 \(O(B(d(V)^2+\sqrt{V}+n\log V))\)。

CF1168E

题目链接

不会证明正确性/yun。

考虑随两个排列 \(p,q\)，我们把所有不合法（即 \(p_i\oplus q_i\neq a_i\)） 的位置丢进队列里。每次随机调整 \(p\) 和 \(q\)。调整一个排列时，拎出来 \(p\) 中数字为 \(q_i\oplus a_i\) 的位置和当前位置 \(i\) 交换。若这次交换使其不合法，则将其加入队列，直到队列被删空为止。

考虑如果出现循环交换的情况怎么办。设定一个阈值 \(B\)，若重构 \(B\) 次仍未成功，则再次随机排列。

无解是 \(\oplus_{i=1}^n a_i\neq0\)，必要性显然，但是我的随机没法证明他充分/zj。