C. 01 串问题

    传统题 1000ms 256MiB

01 串问题

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

小X每天都在玩 repo ,这一天他游戏玩腻了,于是打算写一会儿算法题目放松一下,但是好巧不巧,他写题的时候把子串看成子序列了,导致debug了 11 个小时一直通过不了,幸运的是子序列仍然可做。

题目描述

给定一个长为 nn0101 字符串,再给定两个下标 llrr ,他想知道能否通过反转 [l,r][l,r] 区间内的某些字符,使得字符串中 0101 子序列和 1010 子序列的数量相同。

如果可以的话,输出 "Yes" ,否则输出 "No" 。

* 子序列的定义是从一个数组中删除若干数字之后,重新拼起来的序列。

输入格式

第一行输入一个数字 tt , 代表测试数据组数。

对于每组测试:

  • 第一行输入一个数字 nn

  • 第二行输入一个长度为 nn 的字符串 ss

  • 第三行输入两个下标 l,rl , r

输出格式

对于每组测试数据,输出一行 "Yes" 或者 "No" 。

样例 #1

样例输入 #1

4
2
11
2 2
11
01111111100
8 9
3
101
3 3
4
0101
3 4

样例输出 #1

Yes
No
Yes
Yes

提示

对于20%数据,满足 1n201 \leq \sum n \leq 20

对于50%数据,满足 1n1031 \leq \sum n \leq 10^3

对于100%数据,满足 1n105,si{0,1},11 \leq \sum n \leq 10^5 , s_i \in \{0,1\} , 1 \leq l,rn l ,r \leq n