luogu#P2086. [NOI2012] 魔幻棋盘

    ID: 6134 远端评测题 5000ms 500MiB 尝试: 2 已通过: 1 难度: 7 上传者: 标签>2012线段树NOI 系列二维线段树最大公约数gcd

[NOI2012] 魔幻棋盘

题目描述

将要读二年级的小 Q 买了一款新型益智玩具——魔幻棋盘,它是一个 NNMM 列的网格棋盘,每个格子中均有一个正整数。棋盘守护者在棋盘的第 XX 行第 YY 列(行与列均从 11 开始编号)并且始终不会移动。棋盘守护者会进行两种操作:

  • (a)询问:他会以自己所在位置为基础,向四周随机扩展出一块大小不定的矩形区域,向你询问这一区域内所有数的最大公约数是多少。
  • (b)修改:他会随意挑选棋盘上的一块矩形区域,将这一区域内的所有数同时加上一个给定的整数。

游戏说明书上附有这样一句话“聪明的小朋友,当你连续答对 1993032419930324 次询问后会得到一个惊喜噢!”。小 Q 十分想得到这个惊喜,于是每天都在玩这个玩具。但由于他粗心大意,经常算错数,难以达到这个目标。于是他来向你寻求帮助,希望你帮他写一个程序来回答棋盘守护者的询问,并保证 100%100\% 的正确率。

为了简化问题,你的程序只需要完成棋盘守护者的 TT 次操作,并且问题保证任何时刻棋盘上的数字均为不超过 26212^{62} - 1 的正整数。

输入格式

第一行为两个正整数 N,MN,M,表示棋盘的大小。

第二行为两个正整数 X,YX,Y,表示棋盘守护者的位置。

第三行仅有一个正整数 TT,表示棋盘守护者将进行 TT 次操作。

接下来 NN 行,每行有 MM 个正整数,用来描述初始时棋盘上每个位置的数。

接下来 TT 行,按操作的时间顺序给出 TT 次操作。每行描述一次操作,以一个数字 0011 开头:

  • 若以数字 00 开头,表示此操作为询问,随后会有四个非负整数 x1,y1,x2,y2x_1,y_1,x_2,y_2,表示询问的区域是以棋盘守护者的位置为基础向上扩展 x1x_1 行,向下扩展 x1x_1 行,向左扩展 y1y_1 列,向右扩展 y2y_2 列得到的矩形区域(详见样例)。
  • 若以数字 11 开头,表示此操作为修改,随后会有四个正整数 x1,y1,x2,y2x_1,y_1,x_2,y_2 和一个整数 cc,表示修改区域的上、下边界分别为第 x1,x2x_1,x_2 行,左、右边界分别为第 y1,y2y_1,y_2 列(详见样例),在此矩形区域内的所有数统一加上 cc(注意 cc 可能为负数)。

输出格式

对于每次询问操作,每行输出一个数,表示该区域内所有数的最大公约数。

2 2
1 1
4
6 12
18 24
0 0 0 1 0
1 1 1 1 2 6
1 2 1 2 2 6
0 0 0 1 1
6
6

提示

对于第一、第四次操作(查询操作)后,加粗部分表示查询区域。

对于第二、第三次操作(修改操作)后,加粗部分表示修改区域。

测试数据分为 A、B、C 三类:

A 类数据占 20%20\%,满足 N100N \leq 100M100M \leq 100T2×104T \leq 2\times 10^4

B 类数据占 40%40\%,满足 N=1N = 1M5×105M \leq 5\times 10^5T105T \leq 10^5

C 类数据占 40%40\%,满足 N×M5×105N \times M \leq 5\times 10^5T105T \leq 10^5

在每类数据中,均有 50%50\% 的数据满足每次修改操作仅含一个格子(即 x1=x2x_1 = x_2y1=y2y_1 = y_2)。

输入数据保证满足题目描述中的所有性质。