← 返回题目列表

Codeforces · 575/I

I. 机器人保护

中文机器翻译题面 查看原题

“机器人工业”公司生产用于领土保护的机器人。机器人保护三角形区域——直角等腰三角形,其内向平行于南北和东西方向。

一些土地的所有者购买并在他的领土上设置机器人来保护它。有时,商人想在那片土地上建造办公室,并想知道有多少机器人将守卫它。您将处理这些查询。

输入

第一行包含整数 N — 土地的宽度和高度,以及整数 Q — 要处理的查询数。

接下来的 Q 行包含您需要处理的查询。

两种类型的查询:

1. 1 dir x y len — 添加一个机器人来保护三角形。根据 dir 的值,x、y 和 len 的值代表不同的三角形: dir = 1:三角形由点 (x, y)、(x + len, y)、(x, y + len) 定义 dir = 2:三角形由点 (x, y) 定义, (x + len, y), (x, y - len) dir = 3: 三角形由点定义 (x, y), (x - len, y), (x, y + len) dir = 4: 三角形由点定义(x, y), (x - len, y), (x, y - len)
2. 2 x y — 输出有多少机器人守卫该点(如果该点位于三角形内部或边界上,则机器人守卫该点)

- 1 ≤ N ≤ 5000
- 1 ≤ Q ≤ 105
- 1 ≤ 目录 ≤ 4
- 三角形的所有点都在范围 [1, N] 内
- 所有数字均为正整数

输出

对于每个第二类型查询输出,有多少机器人守卫该点。每个答案都应该在单独的一行中。

示例

输入 #1

17 10
1 1 3 2 4
1 3 10 3 7
1 2 6 8 2
1 3 9 4 2
2 4 4
1 4 15 10 6
2 7 7
2 9 4
2 12 2
2 13 8

输出 #1

2
2
2
0
1