省选-特殊题型-交互题 · Zhl2010 第二博客

配置方法

C++

g++ problem.cpp problem.h grader.cpp -o problem.exe

常见注意事项：

感觉都是人类智慧。

二分答案。对于当前 $mid$ ，每次加数，如果答案大于 $mid$ 就减掉。等到最后判断是否有 $cnt\times mid$ 个数。

需要有各种二分中的继承优化这种东西，还需要 $vis$ 。

为了防止被卡，random_shuffle 一下序列即可。

首先，大概思路肯定是一点一点减。我们先减去第一个数，然后这个数是新的颜色。如果再减一个数，答案不变，就新开颜色，变了，暴力看这个数是什么颜色。

显然复杂度炸了， $nm^2$ 。

我们发现我们需要在 $5$ 次以内找到一个数的颜色。

这让我们联想到了二分，二分现在的集合，然后...做完了？貌似有点问题。

鉴于二分颜色不好写，直接二分在第几个序列，判断后面的序列没有这个颜色可不可以。

注意到 $C_{20}^{10}\ge n$ ，所以我们想到了一种做法，就是询问之后点对之间如果有 $10$ 次在同一个集合中，就有边。

但是这样处理起来会 TLE。

人类智慧：我们发现叶子结点在一半的询问中是单独的连通块，然后处理叶子节点，找出然后删掉。

我们首先需要找到合适的 $k$ ， $1$ 区分不出任何东西，所以我们先尝试 $2$ 。

我们发现对于 $2$ ，可以进行两两配对，我们 $Q(l,r,l)$ 可以求出 $2x,2x+1$ 没有配对的个数。

然后我们想二分出来 $1$ 在左边还是右边的话需要 $Q(1,mid,2),Q(mid+1,n,2)$ ，我们发现一对数对这两个区间的贡献是相同的，要么都是 $0$ ，要么都是 $1$ 。

然后现在的问题就是 $1$ 不可能匹配，还有 $n$ 为偶数的时候 $n$ 也不行。

所以分类讨论：

$n$ 为奇数，可以直接二分， $20$ 次。
$n$ 为偶数，我们只需要在二分到左右相同的时候确定 $n$ 在哪里，用 $Q(,,n)$ 。但是很恶心的就是这需要 $21$ 次。我们能不能优化？我们发现二分到最后一次的时候我们已经知道很多了，设现在是 $l,r$ ，已知 $(1,l+1),(1,l-1),(l+2,n),(l,n)$ 。我们发现 $l,l+1$ 中不是 $1$ 的数一定是跟左边或右边配对的。如果 $(1,l+1)$ 和 $(1,l-1)$ 相同，那么 $x$ 是和 $(l,l-1)$ 里面的数配对的，就直接询问 $(1,l)$ ，不同的情况同理。

这道题是让我们把从快到慢的除了那 $n-1$ 个数的数排序。

容易想到，我们一开始肯定是先分成 $n$ 个栈，然后取出每个栈的最大值的比较，找出当前最大值。我们需要维护每一个栈当前的最大值，每当有一个数被取出，都需要重新把这个栈用别的栈中不是最大值的数填满，然后询问最大值。

这样循环，我们最后需要 $2n^2-n+1$ 场比赛，我们需要优化。

我们尝试把一些需要两次查询的改成只需要一次。我们考虑在最后剩下 $2n-1$ 个数的时候的情况，因为这种情况我们无法从别的栈中找到足够的不是最大值的数。

这种情况中，有 $n$ 个数在自己的那个块内当最大值，还有 $n-1$ 个数是“凑数”的，永远不会被选中，所以我们要考虑在 $n$ 次确定这 $n$ 个数的排序。

方法就是每次选这 $n$ 个数没有被选中的加入询问集合，剩下的用那 $n-1$ 个中的一些补全缺口，然后每次拿出最大的，循环直到这 $n$ 个数只剩一个。

注意：如果你不用 set 写法，需要小心当前栈的数去别的栈当最大值，需要注意这种情况。虽然我就是用的 set。

标签期望+随机化？

首先我们先预处理出来前 $5$ 个点的连边情况，暴力即可。

然后我们可以发现，三个点我们有连个点的关系确定，如果查询出来的减去已知的是 $0/2$ ，那就可以直接确定，否则就需要根据后面的一直推。如果一直是 $1$ 就表示 $j,j+1\cdots i$ 里面 $01$ 交替。