「Codeforces 1090H」Linearization

Codeforces 1090H. Linearization

题意

定义一个长度为 \(n(n=2^k,k\in N)\) 的 01 串 \(s\)（从 0 开始标号）是线性的，当且仅当存在整数 \(x\) 和 二进制数位 \(b\)，使得 \(\forall i\in [0,n),s_i=P(i~{\rm and}~x)~{\rm xor}~b\)，其中 \(P(a)\) 表示 \(a\) 的二进制表示中 \(1\) 的数量的奇偶性

定义一个 01 串的线性化难度为，进行最少的取反一个区间的操作，使之成为线性的操作次数

给定一个长度为 \(m\) 的 01 串 \(t\)，\(q\) 次询问指定一个子串，要求计算其线性化难度

\(m,q\le 2\times 10^5\)