题解：AT_abc380_d [ABC380D] Strange Mirroring

下文下标统一从 0 开始。

定理：如果 \operatorname{bitcount}(i) 为奇数，那么第 i 条字符串是反转字符串，否则是正常字符串。（反转指题目中的大小写互换）

证明：对于 i=0，第 0 条字符串是正常字符串。

对于 i>0，注意到每次操作的本质是将下标二进制向高位扩展了一位，操作后，前半部分这一位都是 0，后半部分这一位都是 1，下标的 \operatorname{bitcount} 奇偶性恰好与其对应位置相反，而字符串是否反转也相反。

算出查询的位置在哪条字符串的什么位置，再根据以上定理得出的反转性回答即可。

时间复杂度 O(n)。