题意： 有n*m个格子(n,m <= 2*10^9)，有k(k<=10^5)个格子中有值，现在有三种操作，第一种为交换两行，第二种为交换两列，交换时只有两行或两列都有格子有值或都没有格子有值时才能交换，第三种操作是询问现在第A行第B列值为多少.
解法：格子太大，但是k比较小，所以考虑离散一下，把行离散出来，最多10^5行，列用map存下即可。
nowR[i] = j 时表示现在的第 i 行是原来的第 j 行， nowC表示列的
R[]表示该行有没有值, CntC[]表示列
然后交换时直交换上面几个东西即可。
查询时先找到nowR[mp[A]], nowC[B]，在对应原来的那一行里面找B即可，普通找不好找，索性预先把每行有的元素存起来，存到一个vector V[10^5]里面，因为要存下，所以行需要离散，然后排个序，以后就可以二分地找了。
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;
#define N 100007 int nowR[N],R[N],b[N];
map<int,int> mp,CntC,nowC;
vector<pair<int,int> > V[N];
struct Point
{
int x,y,c;
}p[N]; int bsearch(int i,int low,int high,int x)
{
while(low <= high)
{
int mid = (low+high)/;
if(V[i][mid].first == x)
return mid;
else if(V[i][mid].first > x)
high = mid-;
else
low = mid+;
}
return low;
} int main()
{
int n,m,k,i,j,T;
int t,cs = ;
int op,A,B;
scanf("%d",&t);
while(t--)
{
mp.clear(); nowC.clear(); CntC.clear();
scanf("%d%d%d",&n,&m,&k);
for(i=;i<=k;i++)
{
V[i].clear();
scanf("%d%d%d",&p[i].x,&p[i].y,&p[i].c);
p[i].x++, p[i].y++;
nowC[p[i].y] = p[i].y;
b[i] = p[i].x;
}
sort(b+,b+k+);
int ind = unique(b+,b+k+)-b-;
for(i=;i<=ind;i++)
mp[b[i]] = i;
memset(R,,sizeof(R));
for(i=;i<=k;i++)
{
int toR = mp[p[i].x];
R[toR]++;
int toC = nowC[p[i].y];
CntC[toC]++;
V[toR].push_back(make_pair(p[i].y,p[i].c));
}
for(i=;i<=ind;i++)
{
nowR[i] = i;
sort(V[i].begin(),V[i].end());
}
scanf("%d",&T);
printf("Case #%d:\n",cs++);
while(T--)
{
scanf("%d%d%d",&op,&A,&B);
A++,B++;
if(op == )
{
int toA = mp[A];
int toB = mp[B];
if((R[toA]&&R[toB]) || (!R[toA]&&!R[toB]))
{
swap(nowR[toA],nowR[toB]);
swap(R[toA],R[toB]);
}
}
else if(op == )
{
if((CntC[A]&&CntC[B])||(!CntC[A]&&!CntC[B]))
{
swap(CntC[A],CntC[B]);
swap(nowC[A],nowC[B]);
}
}
else
{
int nA = nowR[mp[A]];
int nB = nowC[B];
int id = bsearch(nA,,V[nA].size()-,nB);
if(id < || id >= V[nA].size() || V[nA][id].first != nB)
puts("");
else
printf("%d\n",V[nA][id].second);
}
}
}
return ;
}