E. So Mean
题目描述
解法
其实我自己快做出来了，说出来我自己都不信，构造题就是要多观察：
虽然看到这题没什么思路，但是我们可以乱手玩一下，因为询问限制较弱我们就考虑先确定一个数吧，可以询问每组 (n-1) 个数，设没询问的数是 (i)，我们可以提前算出他们的求和是：
不难发现当且仅当 (i=1or i=n) 时回答是YES，由于出题人善良的提示我们知道我们是区分不出来 (1) 和 (n) 的，因为整个数列的值可以全部翻转但还是符合所有的询问，所以随意指定即可，现在我们得到了 (1) 和 (n) 的具体位置。
那么能不能扩展上面的做法呢？能不能用类似的方法确定 (2) 和 (n-1) 呢？假设我们已经确定了 (k) 对这样的数，那么剩下的数是 ([k+1,n-k])，我们询问每组 (n-2k-1) 个数，可以提前计算出求和，技巧是把所有数提出 (k)：
当且仅当 (i=k+1or i=n-k) 的时候回答是 YES，所以我们可以得到 (k+1) 和 (n-k) 的具体位置。
分析一下现在的总操作数：(n+(n-2)+(n-4)...=frac{n^2+2n}{4})，还不能过题。
如果说上面东西还是人能想到的话，下面就是神仙操作了。注意到这题的信息是和取模有关的，可以求算出每个数模某个数的余数，然后用中国剩余定理拼起来，这道题我们选模数 (3,5,7,8)，他们是互质的，而且 (3cdot 5cdot 7cdot 8=840geq 800geq n)，为了能用这些模数我们先用暴力方法处理出前 (8) 个数，消耗 (5n) 步。
考虑怎么求算每个数模 (3) 的余数，我们可以先用 (1,2) 和这个数问一下看是不是 (3) 的倍数，然后用 (1,3) 和这个数问一下看模 (3) 是否为 (2)，剩下的模 (3) 为 (1)，消耗步数 (n+frac{2n}{3})，模 (5) 和 模 (7) 都类似，消耗步数分别是 (n+frac{4n}{5}...+frac{2n}{5}) 和 (n+frac{6n}{7}...+frac{2n}{7})
对于 (8) 我们不能类似地用 (n+frac{7n}{8}...+frac{2n}{8})，由于 (8) 是 (2) 的幂次我们可以考虑倍增，首先花 (n) 步得知它的奇偶性，然后用 (1,2,3) 来区分 (4k) 和 (4k+2)，用 (1,2,4) 来区分 (4k+1) 和 (4k+3)，又花费 (n) 步。我们用 (1,2,3,n-3,n-2,n-1,n) 来区分 (8k) 和 (8k+4)，(8k+1) 和 (8k+5) 等也同理，再花费 (n) 步。
现在计算一下总步数为 (15.324n)，然后这个题变成了大模拟，所以我没打代码。