自动搬运

查看原文

来自洛谷，原作者为

	Natsume_Rin 你知道世界的秘密吗？

搬运于2025-08-24 22:34:47，当前版本为作者最后更新于2021-11-28 11:19:54，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

入 OI 以来做的第二道交互题。

题目传送门

题意简述

有 $n$ 个颜色未知的球，你现在可以通过 $Q$ 次询问，每次询问一个区间 $[l,r]$ 中球的颜色数，需要你确定最后的所有球的颜色异同。

数据范围 $n \leq 1000$，$2000 \leq Q \leq 10000$，$Q$ 的范围与子任务特性有关。

一般性解法

先可以不考虑子任务，考虑 $n=1000,Q=10000$ 时怎么做。

首先我们可以从 $n$ 号球推到 $1$ 号球，假设当前的颜色已经出现了 $k$ 个不同的，分别为 $c_1,c_2,c_3\dots c_k$，它们出现的 最靠前的位置 分别为 $p_1,p_2,p_3\dots p_k$，满足 $p$ 序列升序。

那么假设当前需要求解 $i$ 号球，那么在 $[1,k]$ 中二分一个 $p_{mid}$，可以自行想象一下，如果询问区间 $[i,p_{mid}]$，得到的结果是 $res$，如果

• $res = mid$，那么说明这一个球在颜色 $c_1,c_2,c_3\dots c_{mid}$ 之间，将二分的右端点变为 $mid-1$。
• $res=mid+1$，那么说明这一个球在颜色 $c_{mid+1},c_{mid+2},c_{mid+3}\dots c_k$ 中 或者是一个新颜色，将二分的左端点变为 $mid+1$。
• 好吧，其实没有第三种情况了。

最后就可以通过二分得到答案。这里举一个 $col=[1,3,2,2,2,1]$ 的例子求解 $col_1$ 以便大家理解。

• 当前 $c=[3,2,1]$，$p=[2,3,6]$，二分左右端点为 $[1,3]$。
  • $mid=2$，$p_{mid}=3$，询问 $[1,3]$，$res=3$，说明这一个颜色是 $1$ 或者是一个新颜色 $4$。二分左右端点为 $[3,3]$。
  • $mid=3$，$p_{mid}=6$，询问 $[1,6]$，$res=3$，说明这一个球就是颜色 $1$。
• 最后更新 $c=[1,3,2]$，$p=[1,2,3]$。

这样需要询问 $n \log_2 n$，实测可以通过 $Q=10000$ 的子任务。

数据分治

不知道正解是否需要，但是我的需要。

• $T=2$

颜色段连续，所以对于每一个球 $i$，只需要询问 $[i,i+1]$ 即可知道异同关系。询问次数为 $n-1$。

• $T=3$

照常做，用一般性解法，询问次数大约为 $2n-2$。

• $T=5$

每次询问区间 $[i,n]$，如果 $res_{i,n}=res_{i+1,n}$，那么就二分，否则就是新颜色，询问次数大约为 $n+\log_2 n$。

• $T=4$

有点意思。

当颜色数为 $4$ 时，那么就不可能出现新颜色。一个可能二分的过程是这样的。

• $[1,4]$，$mid=2$。
• $[3,4]$，$mid=3$。
• $[4,4]$，$mid=4$。

你会发现这样子每一个球会询问 $3$ 次，总询问次数约为 $3n$ 无法通过。

怎么优化呢？

突破口就在于 不可能出现新颜色，所以当二分区间 $[l,r]$ 满足 $l=r$ 且颜色数为 $4$ 时，那么 $col_i=c_l$，因为 只有这一种颜色可选，又不可能出现新颜色。这样就可以将询问次数降到 $2n$ 级别，可以通过。

放在最后

很好的一道题。我才不会告诉你我做了很久。 代码就不放了（太丑了）。

完结撒花。