1006. 恋恋的序列

题目描述

古明地恋在雾之湖畔发现了一排 01 石头，她好奇一段区间内数字交替了多少次。她可以无意识赋值或取反一段石头，你需要快速回答她的询问。给定一个长度为 n 的 01 序列 a1, a2, …, an （其中 ai ∈ {0, 1}）。定

义“交替次数”为序列中相邻元素不同的位置数。例如，序列 0101 的交替次数为 3（对应位置对 （1, 2）, （2, 3）, （3, 4））。特别地，当区间长度为 1 时，交替次数为 0。你需要支持三种操作：

• 1 l r x：将区间 [l, r] 内所有元素赋值为 x（x 为 0 或 1）。

• 2 l r：将区间 [l, r] 内所有元素取反（0 变 1，1 变 0）。

• 3 l r：查询区间 [l, r] 内所有元素的交替次数。

输入格式

第一行一个整数 T，表示测试数据组数。 每组数据第一行包含两个整数 n, m，分别表示序列长度和操作次数。 第二行包含 n 个整数

a1, a2, …, an，表示初始序列。 接下来 m 行，每行描述一个操作，

格式如上。数据范围：1 ≤ T ≤ 10，1 ≤ n, m ≤ 2 × 105，所有操作保证区间合法。

输出格式

对于每个查询操作（3），输出一行一个整数，表示对应区间的交替次数。

样例输入

2
6 5
0 1 0 1 0 1
3 1 6
1 2 4 0
3 1 6
2 3 3
3 1 6
10 8
1 0 1 1 1 0 0 0 0 1
1 3 7 1
3 8 9
2 2 10
2 4 7
3 8 10
2 4 9
2 3 4
3 1 8

样例输出

5
1
3
0
1
1

来源：官方题面 PDF（2026"钉耙编程"暑期联赛 第10场）