CF2244E Masha and the Garland

Masha 有一串新年彩灯，共有 $n$ 个灯泡。每个灯泡可以是关的或开的。彩灯的状态由一个长度为 $n$ 的二进制字符串 $s$ 表示，其中 '0' 表示灯泡关闭，'1' 表示灯泡打开。 Masha 认为一串彩灯是美丽的，当且仅当相邻灯泡的状态严格交替。也就是说，没有两个相邻的灯泡同时处于同一状态（即没有连续的两个 '1' 或两个 '0'）。例如，字符串 '01010' 和 '1010' 是美丽的彩灯，而 '0110' 和 '000' 不是。 Yura 可以对彩灯进行如下操作：选择一个子段，将该子段内所有灯泡的状态翻转（将所有开着的灯泡关闭，将所有关闭的灯泡打开）。 Masha 要和 Yura 玩 $q$ 次这样的游戏：每次她选择从第 $l$ 个到第 $r$ 个灯泡（包含两端），Yura 要在不超过 $k$ 次操作内使这个子段成为美丽的彩灯。 然而 Yura 不确定是否一定能做到，所以他请你判断对每次游戏，是否有办法用不超过 $k$ 次操作将选中的区间变成美丽的彩灯。注意，每次游戏之间互不影响，彩灯的原始状态不会被真实地改变。

第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的个数。 每个测试用例的第一行包含两个整数 $n$ 和 $q$（$1 \le n, q \le 2 \times 10^5$），分别表示彩灯的长度和游戏的次数。 第二行是一个只包含 '0' 和 '1' 的长度为 $n$ 的字符串 $s$，表示彩灯的初始状态。 接下来的 $q$ 行，每行包含三个整数 $l$、$r$、$k$（$1 \le l \le r \le n$，$0 \le k \le n$），分别表示区间的左右端点和最多允许的操作次数。 保证所有测试用例中 $n$ 的总和与 $q$ 的总和都不超过 $2 \times 10^5$。

对于每一场游戏，如果能在不超过 $k$ 次操作内将指定区间变为美丽的彩灯，输出 "YES"，否则输出 "NO"。

由 ChatGPT 5 翻译