首页 > 试题广场 >

交换查询

[编程题]交换查询
  • 热度指数：1245 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 128M，其他语言256M
  • 算法知识视频讲解

小M有一个N*M的方格，行列下标均从0开始。其中有K个方格中有数字，表示为(X, Y)方格中有数字C。对方格有2种操作，交换方格的两行或者交换方格的两列。

小M希望随时能够知道在经过一系列交换之后某一方格中是否含有数字，并且如果有的话，数字是多少。


输入描述:
输入数据第一行包含3个整数N, M, K。表示N行M列的方格，并且其中K个方格有数字。
(1 <= N, M <= 10^5, 0 <= K <= 10^5)
接下来K行，每行有3个整数，X, Y, C,表示（X，Y）方格中有数字C。
(0 <= X <= N - 1, 0 <= Y <= M - 1, 1 <= C <= 1000)
接下来有一个整数T，表示有T次操作或询问。(0 <= T <= 10^5)
接下来T行，买行有三个整数Q, A, B。
当Q == 0时，交换行A和行B所有方格。
当Q == 1时，交换列A和列B所有方格。
当Q == 2时，询问(A, B)是否有数字，如果有则输出该数字，如果没有输出－1。
数据保证Q，A，B均在合法的范围之内。


输出描述:
对于每个询问，输出一个整数表示其答案。
示例1

输入

3 3 2
1 1 1
2 2 2
5
2 1 1
0 0 1
1 0 1
2 1 1
2 2 2

输出

1
-1
2

说明

首先有3x3的方格，其中（1，1）有数字1，（2，2）有数字2，即：
-1 -1 -1
-1 1 -1
-1 -1 2
5次操作，
第一次查询（1，1）得到1；
第二次交换行1和行2，即：
-1 1 -1
-1 -1 -1
-1 -1 2
第三次交换列1和列2，即：
1 -1 -1
-1 -1 -1
-1 -1 2
第四次查询（1，1）得到-1；
第五次查询（2，2）得到2；
算法知识视频讲解
开通博客
头像 牛客题解官
发表于 2020-06-05 18:50:02
精华题解 题解： 题目难度：三星 考察点： 哈希表 易错点： 因为和的范围都有，所以不能直接开成的数组，因为这样内存会爆掉，考虑到这是最大也只有，说明这是一个比较稀疏的矩阵，因此可以用来进行存储。 解法： 定义map<pair<int,int>,int>这样一个数据结构来存储方格中的数 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

C++工程师 数组 Momenta 模拟 哈希 2019 Java工程师
来自：Momenta2019...
上传者：小小
难度：
3条回答 5296浏览

热门推荐

通过挑战的用户

查看代码

相关试题

交换查询

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号