E. 优美字符串

    Type: Default 1000ms 256MiB

优美字符串

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

有一天,你发现了一个只由 00 和 11 组成的优美字符串 ss 。

现在,你想对它进行 qq 运算,让它变得更加优美。

每个操作由两个整数 ii ( 1≤i≤∣s∣1 \le i \le |s| ) 和 vv ( v∈{0,1}v \in \{0, 1\} )来描述,这意味着字符串中的第 ii 个字符被赋值为 vv (即执行赋值 si=vs_i = v )。

但你喜欢数字 11001100 ,所以每次查询后,你都想知道这个优美字符串中是否存在子串 1100(即存在 1≤i≤∣s∣−31 \le i \le |s| - 3 和 sisi+1si+2si+3=1100s_{i}s_{i + 1}s_{i + 2}s_{i + 3} = \texttt{1100} 这样的字符串)。

输入格式

第一行包含一个整数 tt ( 1≤t≤1041 \leq t \leq 10^4 ) - 测试用例数。

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

下一行包含一个整数 qq ( 1≤q≤2⋅1051 \leq q \leq 2 \cdot 10^5 ) - 查询次数。

接下来的 qq 行包含两个整数 ii ( 1≤i≤∣s∣1 \leq i \leq |s| ) 和 vv ( v∈{0,1}v \in \{0, 1\} ),用于描述查询。

保证所有测试用例中 ∣s∣|s| 的总和不超过 2⋅1052 \cdot 10^5 。同时保证所有测试用例中 qq 的总和不超过 2⋅1052 \cdot 10^5 。

输出格式

对于每个查询,如果安雅的字符串中有 1100,则输出 YES;否则,输出 NO。

样例 #1

样例输入 #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

子任务数据规模:

对于 20%20 \% 的测试数据,额外满足 1≤∣s∣≤1021 \leq |s| \leq 10^2。

对于 50%50 \% 的测试数据,额外满足 1≤∣s∣≤1041 \leq |s| \leq 10^4。

【Wangzai 月赛(入门组)】第零场

Not Attended
Status
Done
Rule
IOI
Problem
5
Start at
2024-12-10 19:00
End at
2024-12-10 21:00
Duration
2 hour(s)
Host
Partic.
0