思路：将行列离散化，那么就可以用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 = 0; scanf("%d", &tt); while (tt--) { int n, m, k, tailr, tailc; tailr = tailc = 0; scanf("%d%d%d", &n, &m, &k); for (int i = 0; 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 = 0; i < tailr; ++i) e[i].clear(); for (int i = 0; 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 = 0; i < tailr; ++i) sort(e[i].begin(), e[i].end()); for (int i = 0; i < tailr; ++i) r[i] = i; for (int i = 0; i < tailc; ++i) c[i] = i; printf("Case #%d: ", ++ri); int T; scanf("%d", &T); while (T--) { int x, a, b; scanf("%d%d%d", &x, &a, &b); if (x == 1) { 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 == 2) { 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 == 3) { int idr = lower_bound(qr, qr + tailr, a) - qr; if (qr[idr] != a) { puts("0"); continue; } int idc = lower_bound(qc, qc + tailc, b) - qc; if (qc[idc] != b) { puts("0"); 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("0"); continue; } node d=*(it); if(d.col!=c[idc]) { puts("0"); continue; } printf("%d ",d.va); } } } return 0; }