题意：模拟栈的情况，但是这个栈处理的元素是集合。 紫书的思路 将所有集合都编号，用map来进行编号。
set 中的set_union() 取a,b并集到c中去 set_intersection() 同时包含a，b中的元素，将其复制到c中去
#include <cstdio> #include <cstring> #include <iostream> #include <stack> #include <map> #include <set> #include <vector> #include <algorithm> using namespace std; #define ALL(x) x.begin(),x.end() #define INS(x) inserter(x,x.begin()) typedef set<int> Set; map<Set,int> IDcache; vector<Set> Setcache; int Id(Set x) { if(IDcache.count(x)) return IDcache[x]; else { Setcache.push_back(x); return IDcache[x] = Setcache.size()-1; } } int n,t; int main() { scanf("%d",&t); while(t--) { scanf("%d",&n); char op[15]; //IDcache.clear(); //Setcache.clear(); stack<int> S; while(n--) { scanf("%s",op); if(op[0] == 'P') S.push(Id(Set())); else if(op[0] == 'D') S.push(S.top()); else { Set s1 = Setcache[S.top()]; S.pop(); Set s2 = Setcache[S.top()]; S.pop(); Set x; if(op[0] == 'U') set_union(ALL(s1),ALL(s2),INS(x)); if(op[0] == 'I') set_intersection(ALL(s1),ALL(s2),INS(x)); if(op[0] == 'A') { x = s2; x.insert(Id(s1)); } S.push(Id(x)); } printf("%d\n",Setcache[S.top()].size()); } printf("***\n"); } return 0; }