Cekavis's notes

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$