← 返回题目列表

AtCoder · abc406_d

G. 垃圾清除

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

分数: 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