Processing math: 100%
编程题
                智者的考验

题目描述

公元1371年,太祖下令在北极阁上大建庙宇,短短几年,鸡笼山上便建成了帝王庙、关公庙、真武庙、功臣庙、蒋王庙、都城隍庙、卞壶庙、忠烈庙、刘越王庙、曹武惠王庙共十座庙宇,统称为“十庙”。

后来,为了方便人们来鸡笼山进香礼佛,太祖下令疏通了鸡笼山下已淤塞多年的潮沟。于是,便有了“进香河”。

然而并不是所有人都可以来鸡笼山的,太祖在进香河上修建了一座石桥,中间悬挂了一块高RxRy的机关格图(如下图所示)。所有格子都是活动可翻转的,一面是白色,一面是黑色,这里我们用0表示白色,用1表示黑色。初始情况下,所有格子都是白色面朝前的。有Rx+Ry个机关按钮,对应Rx行和Ry列。一个按钮一旦触发,就会引发对应的一行或一列的格子同时翻转。

图片描述 (本图出自洛谷)

同时,善于识天象的谋臣刘基给出了一种黑白状态,称之为“厄运星”。每一位过往前去鸡笼山的人都需要触发且只触发一个按钮,触发后,如果来访者呈“厄运星”形状,则不允许通过。

每一天要来鸡笼山的人数N是事先就知道的,同时天朝神威浩荡,每一位来者一开始总是有很大概率触发编号为1的按钮,我们不妨用数列A1,A2,,AN来表示,问题保证了初始时候的A数列全为1。同时在整个问题中,Ai满足1AiRx+Ry。太祖很关心那些不允许去鸡笼山的人数。于是他时不时就会询问关于“某一段时间内会有多少人不能通过“厄运星”的考验”。然而那些前来鸡笼山的文人墨客并不愿意如此单一的操作。来访者有可能会突然决定修改自己的触发按钮。更麻烦的情况,结伴而来的连续若干人会突然决定修改触发按钮并且都去触发同一个按钮。

现在这麻烦的问题交给了你。

输入描述

第一行有2个数字RxRy表示机关格图的高和宽(如图所示)。之后Rx行每一行Ry个数字,描述了“厄运星”形状,每一个数字都满足非01

之后一行有两个数字,分别为NM,表示人数和询问修改的次数。

之后M行,对应M次询问或修改。每一行先有一个数字t

t0:之后有2个数字dx,表明将Ad修改为x

t1:之后有2个数字lr,表明询问第l个人到第r个人中有多少人触发按钮后会出现“厄运星”形状,从而无法通过。

t2:之后有3个数字l,rx,表明将Al,Al+1,,Ar1,Ar都修改为x

其中,N1000000M120000Rx2Ry3

输出描述

对于每一次询问(即t1的情况),输出单独一行,一个整数描述了在区间[l,r]中满足要求的人数。

输入输出样例

示例 1

>输入

2 3 
0 0 1 
1 1 0 
7 4 
1 1 7 
0 2 3 
0 3 4	
1 1 7

>输出

0
3
查看答案
赣ICP备20007335号-2