← 返回题目列表

Codeforces · 2036/C

C. 安雅和1100

中文机器翻译题面 查看原题

在翻阅远处抽屉里的东西时,安雅发现了一个漂亮的字符串$$$s$$$,仅由零和一组成。

现在她想通过对其执行 $$$q$$$ 操作使其变得更加美丽。

每个操作由两个整数 $$$i$$$ ($$$1 \le i \le |s|$$$) 和 $$$v$$$ ($$$v \in \{0, 1\}$$$) 描述,并且意味着字符串的第 $$$i$$$ 字符被赋予值 $$$v$$$ (即,赋值 $$$s_i = v$$$ 为执行)。

但是 Anya 喜欢数字 $$$1100$$$,所以每次查询后,她都会要求你告诉她子字符串“1100”是否存在于她的字符串中(即存在 $$$1 \le i \le |s| - 3$$$ 使得 $$$s_{i}s_{i + 1}s_{i + 2}s_{i + 3} = \texttt{1100}$$$)。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。

测试用例的第一行包含字符串 $$$s$$$ ($$$1 \leq |s| \leq 2 \cdot 10^5$$$),仅由字符“0”和“1”组成。这里$$$|s|$$$表示字符串$$$s$$$的长度。

下一行包含一个整数 $$$q$$$ ($$$1 \leq q \leq 2 \cdot 10^5$$$) — 查询数。

以下 $$$q$$$ 行包含两个整数 $$$i$$$ ($$$1 \leq i \leq |s|$$$) 和 $$$v$$$ ($$$v \in \{0, 1\}$$$),描述查询。

保证所有测试用例的 $$$|s|$$$ 总和不超过 $$$2 \cdot 10^5$$$。还保证所有测试用例的 $$$q$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个查询,如果 Anya 的字符串中存在“1100”,则输出“YES”;否则,输出“NO”。

您可以在任何情况下输出答案(大写或小写)。例如,字符串“yEs”、“yes”、“Yes”和“YES”将被识别为肯定响应。

示例

输入 #1

4
100
4
1 1
2 0
2 0
3 1
1100000
3
6 1
7 1
4 1
111010
4
1 1
5 0
4 1
5 0
0100
4
3 1
1 1
2 0
2 1

输出 #1

NO
NO
NO
NO
YES
YES
NO
NO
YES
YES
YES
NO
NO
NO
NO