P2086 [NOI2012]魔幻棋盘

    • 108通过
    • 434提交
  • 题目提供者 洛谷
  • 评测方式 云端评测
  • 标签 二维线段树 最大公约数,gcd 线段树 NOI系列 2012 高性能
  • 难度 NOI/NOI+/CTSC
  • 时空限制 5000ms / 512MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

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

    (a)询问:他会以自己所在位置为基础,向四周随机扩展出一块大小不定的矩形区域,向你询问这一区域内所有数的最大公约数是多少。

    (b)修改:他会随意挑选棋盘上的一块矩形区域,将这一区域内的所有数同时加上一个给定的整数。

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

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

    输入输出格式

    输入格式:

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

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

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

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

    接下来T行,按操作的时间顺序给出T次操作。每行描述一次操作,以一个数字0或1开头: 若以数字0开头,表示此操作为询问,随后会有四个非负整数x1,y1,x2,y2,表示询问的区域是以棋盘守护者的位置为基础向上扩展x1行,向下扩展y1行,向左扩展x2列,向右扩展y2列得到的矩形区域(详见样例)。 若以数字1开头,表示此操作为修改,随后会有四个正整数x1,y1,x2,y2和一个整数c,表示修改区域的上、下边界分别为第x1,x2行,左、右边界分别为第y1,y2列(详见样例),在此矩形区域内的所有数统一加上c(注意c可能为负数)。

    输出格式:

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

    输入输出样例

    输入样例#1: 复制
    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
    输出样例#1: 复制
    6
    6

    说明

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

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

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

    A 类数据占 20%,满足 N ≤ 100,M ≤ 100,T ≤ 20000。

    B 类数据占 40%,满足 N = 1,M ≤ 500000,T ≤ 100000。

    C 类数据占 40%,满足 N * M ≤ 500000,T ≤ 100000。

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

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

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。