交换查询

题解：

题目难度：三星

考察点： 哈希表

易错点：

因为和的范围都有，所以不能直接开成的数组，因为这样内存会爆掉，考虑到这是最大也只有，说明这是一个比较稀疏的矩阵，因此可以用来进行存储。

解法：

定义map<pair<int,int>,int>这样一个数据结构来存储方格中的数字。定义两个数组和，分别表示行号和列号，初始化行号为，初始化列号为。

如图所示，每次交换行和，实质上相当于交换和中的值，相当于它们对应的行号发生变化。

同理如图所示，每次交换列和，实质上相较于交换和中的值，相当于它们对应的列号发生变化。

而对于操作，只需要查询和即可，因为在前面的交换中，已经正确完成了行号和列号的对应关系。整个算法时间复杂度为

#include "bits/stdc++.h"
using namespace std;
typedef pair<int,int> P;
const int maxn=1e5+10;
int x[maxn],y[maxn];
int n,m,k,c;
map<P,int>mp;

int main()
{
    //freopen("in.txt","r",stdin);
    scanf("%d%d%d",&n,&m,&k);
    for(int i=0;i<k;i++){
        P t;
        int a,b,num;
        scanf("%d%d%d",&a,&b,&num);
        t.first=a,t.second=b;
        mp[t]=num;
    }
    for(int i=1;i<n;i++) x[i]=i;
    for(int j=1;j<m;j++) y[j]=j;
    scanf("%d",&c);
    while(c--){
        int op,a,b;
        scanf("%d%d%d",&op,&a,&b);
        if(op==0){
            swap(x[a],x[b]);
        }else if(op==1){
            swap(y[a],y[b]);
        }else{
            P t;
            t.first=x[a],t.second=y[b];
            if(mp.find(t)==mp.end()) printf("-1\n");
            else printf("%d\n",mp[t]);
        }
    }
    return 0;
}