分数: 400 点
问题陈述
有一个网格 H 行和 W 列。让 (i, j) 表示位于 i从顶部开始的第行和 j左起第 列。
有 N 网格上的垃圾;的 i- 第一块位于单元格 (X_i, Y_i).
你被给予 Q 查询,您必须按顺序处理这些查询。每个查询都属于以下类型之一:
-
类型 1:以格式给出 输入
1 x。报告垃圾数量 x- 第行。然后,所有垃圾碎片 x第行已从网格中删除。 -
类型 2:以格式给出 输入
2 y。报告垃圾数量 y- 第列。然后,所有垃圾碎片 y第列已从网格中删除。
约束
- 1 \leq H, W, N \leq 2 \times 10^5
- 1 \leq X_i \leq H
- 1 \leq Y_i \leq W
- If i \neq j,那么 (X_i, Y_i) \neq (X_j, Y_j).
- 1 \leq Q \leq 2 \times 10^5
- 对于类型 1 查询, 1 \leq x \leq H.
- 对于类型 2 查询, 1 \leq y \leq W.
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
H W N
X_1 Y_1
X_2 Y_2
\vdots
X_N Y_N
Q
\text{query}_1
\text{query}_2
\vdots
\text{query}_Q
在这里, \text{query}_i 表示 i-th 查询,以下列格式之一给出:
1 x
2 y
输出
输出 Q 行。的 i- 第行应包含对 i第一个查询。
示例输入 1
3 4 5 1 2 1 3 3 4 3 1 2 2 5 1 1 1 2 2 2 2 4 1 2
示例输出 1
2 1 0 1 0
最初,垃圾碎片位于牢房内 (1, 2), (1, 3), (3, 4), (3, 1), (2, 2).
在第一个查询中,第一行包含两件垃圾,位于 (1, 2) 和 (1, 3),所以报告 2。然后将这些碎片移除;剩余的垃圾位于 (3, 4), (3, 1), (2, 2).
在第二个查询中,第二行包含一件垃圾,位于 (2, 2),所以报告 1。然后将这块部件移除;剩余的垃圾位于 (3, 4), (3, 1).
在第三个查询中,第二列不包含垃圾,因此报告 0.
在第 4 个查询中,第 4 列包含一件垃圾,位于 (3, 4),所以报告 1。然后将这块部件移除;剩余的垃圾位于 (3, 1).
在第 5 个查询中,第 2 行不包含垃圾,因此报告 0.
示例输入 2
1 2 1 1 2 7 2 1 2 1 2 1 2 1 2 1 2 1 2 1
示例输出 2
0 0 0 0 0 0 0
示例输入 3
4 4 16 1 1 1 2 1 3 1 4 2 1 2 2 2 3 2 4 3 1 3 2 3 3 3 4 4 1 4 2 4 3 4 4 7 2 1 1 1 2 2 1 2 2 3 1 3 2 4
示例输出 3
4 3 3 2 2 1 1