思路：将行列离散化，那么就可以用vector 存下10W个点 ，对于交换操作 只需要将行列独立分开标记就行 。
r[i] 表示第 i 行存的是 原先的哪行 c[j] 表示 第 j 列 存的是原先的哪列。
查询只需要一个二分即可。
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#define MAXN 100050
using namespace std;
int r[MAXN], c[MAXN];
struct info {
int x, y, z;
} s[MAXN];
struct node {
int va;
int col;
};
bool operator<(node a, node b) {
return a.col < b.col;
}
vector<node> e[MAXN];
int qr[MAXN];
int qc[MAXN];
int main() {
int cntr, cntc, tt, ri = ;
scanf("%d", &tt);
while (tt--) {
int n, m, k, tailr, tailc;
tailr = tailc = ;
scanf("%d%d%d", &n, &m, &k);
for (int i = ; i < k; ++i) {
scanf("%d%d%d", &s[i].x, &s[i].y, &s[i].z);
qr[tailr++] = s[i].x;
qc[tailc++] = s[i].y;
}
sort(qr,qr+tailr);
sort(qc,qc+tailc);
tailr = unique(qr, qr + tailr) - qr;
tailc = unique(qc, qc + tailc) - qc;
for (int i = ; i < tailr; ++i)
e[i].clear();
for (int i = ; i < k; ++i) {
int x = lower_bound(qr, qr + tailr, s[i].x) - qr;
int y = lower_bound(qc, qc + tailc, s[i].y) - qc;
node d;
d.col = y;
d.va = s[i].z;
e[x].push_back(d);
}
for (int i = ; i < tailr; ++i)
sort(e[i].begin(), e[i].end());
for (int i = ; i < tailr; ++i)
r[i] = i;
for (int i = ; i < tailc; ++i)
c[i] = i;
printf("Case #%d:\n", ++ri);
int T;
scanf("%d", &T);
while (T--) {
int x, a, b;
scanf("%d%d%d", &x, &a, &b);
if (x == ) {
int idr = lower_bound(qr, qr + tailr, a) - qr;
if (qr[idr] != a)
continue;
int idc = lower_bound(qr, qr + tailr, b) - qr;
if (qr[idc] != b)
continue;
swap(r[idr], r[idc]);
}
if (x == ) {
int idr = lower_bound(qc, qc + tailc, a) - qc;
if (qc[idr] != a)
continue;
int idc = lower_bound(qc, qc + tailc, b) - qc;
if (qc[idc] != b)
continue;
swap(c[idr], c[idc]);
}
if (x == ) {
int idr = lower_bound(qr, qr + tailr, a) - qr;
if (qr[idr] != a)
{
puts("");
continue;
}
int idc = lower_bound(qc, qc + tailc, b) - qc;
if (qc[idc] != b)
{
puts("");
continue;
}
node cc;
cc.col=c[idc];
vector<node>::iterator it=lower_bound(e[r[idr]].begin(),e[r[idr]].end(),cc);
if(it==e[r[idr]].end())
{
puts("");
continue;
}
node d=*(it);
if(d.col!=c[idc])
{
puts("");
continue;
}
printf("%d\n",d.va);
}
}
}
return ;
}