CF2049E Broken Queries 题解

感觉这题很聪明，赛时切这题的人是怎么想到的（

考虑分类 $1$ 的位置：若确定 $1$ 在序列左半边还是右半边，则必然能找出长度 $\le\frac{n}{2}$ 的区间使得该区间正确的和为 $0$，长度 $>\frac{n}{2}$ 的区间使得该区间正确的和为 $1$，这个时候直接简单二分即可。问题在于确定 $1$ 在左边还是右边。

考虑询问区间 $[1,\frac{n}{4}]$ 和 $[\frac{n}{4}+1,\frac{n}{2}]$。有一个关键性质：两个区间的长度相同，要么都说谎要么都不说谎。此时继续分类讨论：若两次询问出的结果不同，则显然两个区间中必然有恰好一个实际值为 $1$，即 $1$ 在序列的左半边，否则两个区间的实际值都必须为 $0$，即 $1$ 在序列的右半边。于是就做完了。代码。