#P17905. Triangle Grid
Triangle Grid
把一个边长为 的正三角形按单位长度划分成三角网格,其中有 个边长为 的小三角形。每个小三角形内有一个数,初始均为 。
网格顶点按行编号:最上方是第 行,底边是第 行。第 行有 个顶点,从左到右编号 ,记作 。
一次操作的区域是沿网格线的等边三角形,用 type,x,y,d 指定, 是边长:
type=0:朝上,三个顶点是 ;type=1:朝下,三个顶点是 。
因此, 始终是与水平底边相对的尖顶。区域包含其中所有完整的单位小三角形,两种朝向的小三角形都计入。
支持两种操作:opt=1 给区域内每个小三角形的数加上 ;opt=2 求区域内所有数的和。每次查询仅受之前的修改影响。
输入格式
第一行给出 ,,。
接下来 行,每行先给出 opt type x y d。若 opt=1,再给出 。
其中 ,,,,,。
保证每个指定三角形完整位于大三角形内。等价地,朝上时 ;朝下时 且 。
输出格式
每次查询输出一行整数,为区域和对 取模后的非负余数。
样例 1
输入
5 5
1 0 3 3 2 2
1 1 6 4 2 3
2 0 1 1 5
2 0 3 2 3
2 1 5 3 2
输出
20
11
3
样例 2
输入
10 10
1 0 1 1 5 2
1 1 3 2 1 6
1 1 6 4 2 1
2 0 10 3 1
2 1 5 2 1
2 1 6 4 2
1 0 7 7 1 7
1 1 9 3 1 3
1 0 9 5 2 4
2 0 6 1 2
输出
0
2
12
0