1 #include <
set>
2 #include <
string>
3 #include <vector>
4 #include <map>
5 #include <stack>
6 #include <iostream>
7 #include <algorithm>
8 #define ALL(x) x.begin(), x.end()
9 #define INS(x) inserter(x, x.begin())
10 11 using namespace std;
12 13 typedef
set<
int> Set;
14 map<Set,
int> IDCache;
15 vector<Set> Setcache;
16 // 主要的想法是能想到用map<set<int>, int>这种数据结构来把集合映射成整数
17 // 关键实现在ID函数，对于给定的set<int>都能返回一个唯一编号、vector虽然不能保证元素的唯一性。
18 // 但是我们可以先对map进行检查来保证vector中元素的唯一性，这样每个元素就能唯一编号，刚好可以利用他们的整数索引。
19 // 其中set_union、set_intersection中得实现原理不是重点，先学会怎么用才是重点。
20 // ID函数实现了对新的集合存储，并且
21 int ID(Set x);
22 int main() {
23 24 25 stack<
int> s;
26 int t, n;
27 string op;
28 cin >> t;
29 while (t--) {
30 cin >> n;
31 IDCache.clear();
32 Setcache.clear();
33 for (
int i = 0; i < n; i++) {
34 35 cin >> op;
36 if (op[0] == 'P') s.push(ID(Set()));
// Set()就是空集
37 else if(op[0] == 'D') s.push(s.top());
38 else {
39 40 Set x1 = Setcache[s.top()]; s.pop();
41 Set x2 = Setcache[s.top()]; s.pop();
42 Set x;
43 if (op[0] == 'U') set_union (ALL(x1), ALL(x2), INS(x));
44 if (op[0] == 'I') set_intersection (ALL(x1), ALL(x2), INS(x));
45 if (op[0] == 'A') { x = x2; x.insert(ID(x1)); }
46 s.push(ID(x));
47 48 }
49 50 cout << Setcache[s.top()].size() << endl;
51 }
52 cout << "***" << endl;
53 54 }
55 return 0;
56 }
57 58 // 相当于数据库中得auto_increment, 返回一个唯一的ID值
59 int ID(Set x) {
60 61 if (IDCache.count(x))
return IDCache[x];
62 Setcache.push_back(x);
63 return IDCache[x] = Setcache.size() - 1;
64 65 }