4336. [国家集训队 2026]异形工厂

【题目描述】

在异形工厂里，有一种叫“轮换器”的工具。使用一次轮换器可以将一个 01 串中长度**恰好为 $3$** 的子串循环移位，即将 $xyz$ 替换为 $yzx$ 或 $zxy$。  

给定长度为 $n$ 的 01 串 $s, t$。有 $q$ 次询问，每次询问会给定 $l, r$，求最少需要使用多少次轮换器才能将 $s[l,r]$ 变为 $t[l,r]$。

【输入格式】

输入的第一行包含两个正整数 $n, q$，分别表示字符串 $s, t$ 的长度和询问次数。  

输入的第二行包含一个长度为 $n$ 的 01 字符串 $s$。

输入的第三行包含一个长度为 $n$ 的 01 字符串 $t$。  

输入的第 $i+3$ ($1 \le i \le q$) 行包括两个正整数 $l, r$，表示第 $i$ 次询问。

【输出格式】

对于每次询问，输出一行一个整数表示使用轮换器的最少次数。特别地，若无论如何都无法将 $s[l,r]$ 变为 $t[l,r]$，则输出 $-1$。

【样例 1 输入】

10 5
1010111000
1111000001
1 6
3 5
4 5
1 10
8 9

【样例 1 输出】

3
1
-1
5
0

【样例说明】

对于第一次询问，一种可能的操作方式为：  

1. 选择子串 $[4,6]$，将 $011$ 替换为 $110$，得到 $101110$；  

2. 选择子串 $[2,4]$，将 $011$ 替换为 $110$，得到 $111010$；  

3. 选择子串 $[4,6]$，将 $010$ 替换为 $100$，得到 $111100$。

【数据规模与约定】

对于所有测试数据，均有：  

- $1 \le n, q \le 5 \times 10^5$；  

- 对于所有 $1 \le i \le n$，均有 $s_i, t_i \in \{0,1\}$；  

- $1 \le l \le r \le n$。

特殊性质 A：对于所有 $1 \le i \le \lfloor \frac{n+1}{2} \rfloor$，均有 $s_{2i-1} = t_{2i-1} = 0$。

【来源】

IOI2026中国国家集训队集中培训 Day1 Task1