题目内容

小蓝负责布置一条长廊的彩灯，彩灯排成一列，从左到右编号为 $1$ 到 $n$。每盏灯的初始状态用一个二进制字符描述，'1' 表示亮，'0' 表示灭。 为了让灯光效果左右对称，小蓝希望将彩灯的状态调整成回文序列，即第 $i$ 盏和第 $n-i+1$ 盏的状态相同。

她每次操作可以选择一个区间 $[l, r]$（$1 \le l \le r \le n$），并切换该区间内所有灯的状态：亮的变灭，灭的变亮。 请你帮小蓝计算最少需要多少次操作，才能使所有彩灯的状态变成回文序列。

约束：测试数据组数 $T$ 满足 $1 \le T \le 10^4$。每组彩灯的数量 $n$ 满足 $1 \le n \le 2 \times 10^5$。所有测试数据的 $n$ 之和不超过 $2 \times 10^5$。

开通会员即可查看完整视频题解： 1.题目讲解 2.思路分析 3.逐行代码手写