luogu#P8460. 「REOI-p1」按摩

「REOI-p1」按摩

题目背景

出题人:LinkyChristian

验题人:Legitimity

文案:小糯米

题目描述

无论是勇者还是妖精,在执行任务时,都难免会患上一些特有的“职业病”。其中,在这份“常见勇者职业病名单”上排名第一的,叫作“急性魔力中毒”。虽然魔力中毒在表面上只是类似于发高烧的症状,但倘若没有每次根除,就会变成痼疾,身体马上就会超出负荷极限。魔力中毒的治疗方案,说起来倒是颇为实在:找到魔力淤积的部位,用力按压,利用类似中医按摩的原理,将其淤积点给揉开。具体的治疗原理如下:

人体的魔力脉络,可以视作一个 n×nn \times n 的网格。与中医腧穴中的经穴、经外穴分类类似,魔力的作用“穴位”,亦可以大致上分为阴性和阳性。为了更直观的叙述,我们不妨将阳性的魔力穴位在网格上用黑点表示。而魔力出现淤积,大概率的情形下便是因使用魔力导致肌肉紧绷,从而使得本是阴性的穴位变为阳性,或者阳性变为阴性的结果。所谓的按摩,其实就是将其恢复到其应有的状态,从而疏通魔力。判断按摩是否完成的标志,便是在这个网格中,是否存在一个以黑点作为顶点的所有边均平行于网格的多边形。

现在,经过了一场激烈的战斗,珂朵莉因使用魔力过度,又出现了急性魔力中毒的症状。在给珂朵莉检查身体的时候,威廉发现,在珂朵莉的魔力脉络上,有 mm 个魔力穴位呈阳性反应。现在他要进行 kk 次按摩,每次的按摩都会给出一个点,如果该点的穴位呈阳性则变为阴性,反之则成为阳性。

威廉想知道,在每一次按摩结束后,他的治疗是否已经完成。


形式化题面:给出一个 n×nn \times n 的网格,其中有 mm 个点为黑点。

共有 kk 个操作,每次操作使一个点黑白反转。判断在每次操作结束后是否存在一个以黑点作为顶点的所有边均平行于网格的多边形。

输入格式

第一行两个数:n,mn,m
接下来 mm 行,每行两个数 x,yx,y,表示点 (x,y)(x,y) 为黑点。
下一行输入一个数 kk ,接下来 kk 行,每行两个数 x,yx,y ,表示对点 (x,y)(x,y) 进行一次操作(即按摩)。

输出格式

输出 kk 行,每行一个 YesNo 表示该次操作后治疗是否完成,即在每次操作结束后是否存在一个以黑点作为顶点的所有边均平行于网格的多边形。

100 3
1 1
2 2
1 2
5
5 5
2 1
2 1
5 1
2 5
No
Yes
No
No
Yes

提示

对于样例1,初始状态为

之后每次操作后状态依次为

对于 5%5\% 的数据,n10,m5,k100n\le 10,m\le 5,k\le 100
对于 10%10\% 的数据,n,k100n,k\le 100
对于 20%20\% 的数据,n,k1000n,k\le 1000
对于 80%80\% 的数据,n,k5×104n,k\le 5\times10^4
对于另外 10%10\% 的数据,k=1k=1
对于 100%100\% 的数据,mn105,k105m\le n \le 10^5,k\le 10^5