C. Cards Query Problem
题意：有一些盒子，每次操作有以下三种：把数 \(i\) 扔到集合 \(j\) 内；查询某个集合里的所有数（升序）（可重）；查询包含某个数的集合（升序）（去重）。保证输出的数个数在 \(2\times 10^5\) 内。
可以维护两个 map 套 set，分别表示盒子的数和数的盒子，其中盒子的数用 multiset，数的盒子用 set。每次插入就同时往两个桶里扔，查询就输出一个桶即可。
By cxm1024
#include <bits/stdc++.h>
using namespace std;
signed main() {
int n, q;
scanf("%d%d", &n, &q);
map<int, multiset<int> > mp1;
map<int, set<int> > mp2;
while (q--) {
int op, x, y;
scanf("%d%d", &op, &x);
if (op == 1) {
scanf("%d", &y);
mp1[y].insert(x), mp2[x].insert(y);
}
else if (op == 2) {
for (int tmp : mp1[x])
printf("%d ", tmp);
puts("");
}
else {
for (int tmp : mp2[x])
printf("%d ", tmp);
puts("");
}
}
return 0;
}
同样可以使用 map 套 vector，每次输出时暴力排序（可能去重）后输出。因为输出总数的限制，所以复杂度不会有问题。
By noimi
int main() {
INT(n, q);
constexpr int N = 200001;
vector<vi> a(N), b(N);
rep(q) {
INT(t);
if(t == 1) {
INT(i, j);
a[j].eb(i);
b[i].eb(j);
} else if(t == 2) {
INT(i);
SORT(a[i]);
OUT(a[i]);
} else {
INT(i);
UNIQUE(b[i]);
OUT(b[i]);
}
}
}