#2993. 输出满足特定条件的格子 II
-
ID: 2993
传统题
2000ms
128MiB
尝试: 0
已通过: 0
难度: (无)
上传者:
18779948623
标签> 输出满足特定条件的格子 II
说明
在一个 n*m 的矩阵（矩阵中左上角为第 0 行第 0 列）中，有 k 个格子被涂黑，其他均为白色。现在有 q 次询问，且询问有两种：- 第一种：输出第 x 行的所有被涂黑的格子的列号。
- 第二种：输出第 x 列的所有被涂黑的格子的行号。
输入格式
第一行为 4 个数 n,m,k,p，含义如前所示。接下来 k 行每行两个整数 x,y，表示矩阵中第 x 行第 y 列的格子被涂黑。保证任意两个格子不重复。
接下来 q 行每行两个整数 p,x，若 p 为 1 表示第一种询问，p 为 2 表示第二种询问。
输出格式
按照询问的要求输出。若有多个满足条件的格子，按照这些格子的行号或者列号从小到大的顺序输出。样例
5 5 10 4
3 1
5 4
5 1
3 2
1 2
4 3
5 5
2 4
5 2
4 5
1 3
2 2
1 5
2 3
1 2
1 3 5
1 2 4 5
4
提示
数据范围- 1<= n,m,p <= 10^5, 1<=k<=min(5*10^5, n*m)。
- 数据保证所有询问中输出的格子总个数不超过 5*10^6。