#P17830. [Ontak2022]MUL

[Ontak2022]MUL

题目描述

一个 N×MN\times M 的矩形棋盘被分成单位格,每格属于 KK 名玩家中的一人。一次操作只改变一个格子的所有者,允许某名玩家没有任何格子。

棋盘合法当且仅当同时满足:

  1. 每名玩家的全部格子通过四连通相连,即相邻两格必须共边;空集合也允许。
  2. 任意玩家不能把其他玩家完全包围。具体地,对于任意属于玩家 kk 的格子和任意 l≠kl\ne k,都必须存在一条通向棋盘边界的路径,路径不经过玩家 ll 的任何格子,相邻两格允许共边或共角,即按八连通行走。

已知初始棋盘合法。依次检查 QQ 个提议:如果按提议改变所有者后棋盘合法,则接受并执行;否则拒绝,棋盘保持原状。

输入格式

第一行四个整数 N,M,K,QN,M,K,Q。

接下来 NN 行,每行 MM 个 [1,K][1,K] 内的整数,表示初始所有者。

接下来 QQ 行,每行三个整数 xi,yi,kix_i,y_i,k_i,表示把第 xix_i 行、第 yiy_i 列改归玩家 kik_i。

输出格式

对每个提议输出一行:接受则输出 YES,拒绝则输出 NO。

数据范围

1≤N,M≤10001\le N,M\le1000;2≤K≤1062\le K\le10^6;1≤Q≤1061\le Q\le10^6;1≤xi≤N1\le x_i\le N,1≤yi≤M1\le y_i\le M,1≤ki≤K1\le k_i\le K。初始状态保证合法;把格子改为原所有者也是允许出现的提议。

子任务

子任务 附加限制 分值
1 N=1 7
2 N=2 11
3 N=3 13
4 K≤4 且 Q≤10 17
5 Q≤10 19
6 无额外限制 33

样例 1

输入:

3 4 4 6
1 1 1 1
1 2 2 1
1 1 1 3
3 4 1
3 4 2
3 4 3
3 4 4
2 2 1
1 1 3

输出:

NO
NO
YES
YES
YES
YES