3931: 黑白反转(black)

black.in/out

这是一道描述很直接的题目.

给出一个n*n的二维矩阵, 初始全为白色(用0表示).有以下3种操作:

1. hang L R  表示把第L行到第R行所有元素黑白反转(0变成1,1变成0)

2. lie L R   表示把第L列到第R列所有元素黑白反转(0变成1,1变成0)

3. chaxun x1 x2 y1 y2 查询第x1行到第x2行,第y1列到第y2列组成的矩形区域内有多少个格子为黑色(也就是有多少格子数值为1)

你所要做的就是依次处理这些操作,并对所有的第三类操作,输出查询的结果

【数据范围】

第1,2个测试点,n<=200,m<=200

第3,4个测试点,没有第1类操作”hang”

第5,6,7个测试点,所有第3类操作”chaxun”满足x1=x2,y1=y2

全部测试点,n<=200000,m<=200000,1<=x1<=x2<=n,1<=y1<=y2<=n,1<=L<=R<=n 

第一行两个整数n,m,表示矩阵的大小为n,共m次操作.

接下来m行,每行表示一个操作,每个操作都由一个字符串开头.

如果开头的字符串是hang,后面两个整数L,R表示反转的行的范围.

如果开头的字符串是lie,后面两个整数L,R表示反转的列的范围.

如果开头的字符串是chaxun,后面四个整数x1 x2 y1 y2表示查询的行的范围是从x1到x2, 列的范围是从y1到y2.

对每个chaxun操作,输出一行一个整数ans表示[x1,x2]行,[y1,y2]列这个矩形区域内黑色格子的个数.

10 10
lie 4 7 
lie 5 6 
hang 1 1 
chaxun 1 5 1 2 
hang 3 4 
lie 1 8 
chaxun 7 7 2 7 
chaxun 2 4 2 5 
chaxun 3 6 1 6 
hang 1 6

2
4
5
12