CSG-CPC
Online Judge

1247 : 四国军棋

         Time Limit: 2 Sec     Memory Limit: 512 Mb     Submitted: 261     Solved: 74    

Description

四国军棋是一款有趣的桌游。这里我们考虑一个简化的版本,其有两个玩家小 A 和小 B,棋子是 \([1, 10^5]\) 内的整数。游戏过程如下:

  • 初始,小 A 有 \(n_1\) 个棋子,构成序列 \(A\);小 B 有 \(n_2\) 个棋子,构成序列 \(B\)\(A\)\(B\) 均为给定的,小 A 和小 B 不能修改。
  • 两人派出序列中的第一个棋子,不妨假设分别为 \(x,y\),然后进行战斗。
    • \(x>y\),即小 A 更大,则小 B 的棋子进入弃子堆,之后无法再被使用,然后小 B 派出序列中的下一个棋子,继续进行战斗;
    • \(y>x\),即小 B 更大,则小 A 的棋子进入弃子堆,之后无法再被使用,然后小 A 派出序列中的下一个棋子,继续进行战斗;
    • \(x=y\),即双方一样大,双方的棋子都进入弃子堆,无法再被使用,双方派出序列中的下一个棋子,继续进行战斗。
  • 在战斗过程中,若某一玩家需要派出棋子时没有任何剩余棋子,此时该玩家判负,另一玩家获胜。
    • 特别地,若两方都需要派出棋子但两方都没有任何剩余棋子,则判和。

你可以参考样例解释理解该游戏过程。

小 A 和小 B 是好朋友,他们不希望在游戏中分出胜负,一个平局会让他们更高兴。

给出初始的游戏局面和 \(m\) 次修改,每次修改中,某个序列中的某个棋子会被替换成其他棋子,每次修改的效果会在这次修改之后保留。

每一次修改后,他们希望你能帮他们分析出,如果按照该序列进行游戏,游戏结果是否为平局。

Input

第一行一个正整数 \(n_1\)\(1\leq n_1\leq 10^5\))表示小 A 的棋子个数。

第二行 \(n_1\) 个正整数 \(a_1,a_2,\dots,a_n\)\(1 \le a_i \le 10^5\))描述序列 \(A\)

第三行一个正整数 \(n_2\)\(1\leq n_2\leq 10^5\))表示小 B 的棋子个数。

第四行 \(n_2\) 个正整数 \(b_1,b_2,\dots,b_n\)\(1 \le b_i \le 10^5\))描述序列 \(B\)

第五行一个正整数 \(m\)\(1\leq m\leq 2\times 10^5\))描述修改个数。

之后 \(m\) 行,每行三个正整数 \(o,x,y\)\(1\leq o\leq 2\)\(1 \le x \le n_o\)\(1 \le y \le 10^5\)),意义如下:

  • \(o=1\) 表示将 \(a_x\) 修改为 \(y\)
  • \(o=2\) 表示将 \(b_x\) 修改为 \(y\)

Output

对于每次修改输出一行,如果游戏结果为平局输出 YES,否则输出 NO

Sample

5
1 2 3 4 5
5
5 4 3 2 1
8
1 1 5
1 4 2
1 2 4
1 5 1
1 5 5
2 1 4
2 3 5
2 5 5
NO
NO
NO
YES
NO
NO
NO
YES

Hint

【样例解释 #0】

对于第一次修改,\(A = \{5, 2, 3, 4, 5\}\)\(B = \{5, 4, 3, 2, 1\}\),游戏过程如下:

  1. 小 A 派出 \(a_1 = 5\),小 B 派出 \(b_1 = 5\)
  2. \(a_1 = 5 = b_1 = 5\),都进入弃子堆,小 A 派出 \(a_2 = 2\),小 B 派出 \(b_2 = 4\)
  3. \(a_2 = 2 < b_2 = 4\)\(a_2\) 进入弃子堆,小 A 派出 \(a_3 = 3\)
  4. \(a_3 = 3 < b_2 = 4\)\(a_3\) 进入弃子堆,小 A 派出 \(a_4 = 4\)
  5. \(a_4 = 4 = b_2 = 4\),都进入弃子堆,小 A 派出 \(a_5 = 5\),小 B 派出 \(b_3 = 3\)
  6. \(a_5 = 5 > b_3 = 3\)\(b_3\) 进入弃子堆,小 B 派出 \(b_4 = 2\)
  7. \(a_5 = 5 > b_4 = 2\)\(b_4\) 进入弃子堆,小 B 派出 \(b_5 = 1\)
  8. \(a_5 = 5 > b_5 = 1\)\(b_5\) 进入弃子堆,小 B 需要派出棋子但没有棋子,因此结果不是平局,输出 NO

对于最后一次修改,\(A = \{5, 4, 3, 2, 5\}\)\(B = \{4, 4, 5, 2, 5\}\),游戏过程如下:

  1. 小 A 派出 \(a_1 = 5\),小 B 派出 \(b_1 = 4\)
  2. \(a_1 = 5 > b_1 = 4\)\(b_1\) 进入弃子堆,小 B 派出 \(b_2 = 4\)
  3. \(a_1 = 5 > b_2 = 4\)\(b_2\) 进入弃子堆,小 B 派出 \(b_3 = 5\)
  4. \(a_1 = 5 = b_3 = 5\),都进入弃子堆,小 A 派出 \(a_2 = 4\),小 B 派出 \(b_4 = 2\)
  5. \(a_2 = 4 > b_4 = 2\)\(b_4\) 进入弃子堆,小 B 派出 \(b_5 = 5\)
  6. \(a_2 = 4 < b_5 = 5\)\(a_2\) 进入弃子堆,小 A 派出 \(a_3 = 3\)
  7. \(a_3 = 3 < b_5 = 5\)\(a_3\) 进入弃子堆,小 A 派出 \(a_4 = 2\)
  8. \(a_4 = 2 < b_5 = 5\)\(a_4\) 进入弃子堆,小 A 派出 \(a_5 = 5\)
  9. \(a_5 = 5 = b_5 = 5\),都进入弃子堆,双方需要派出棋子且都没有棋子,因此结果为平局,输出 YES

Author

THU