1 #include "iostream" 2 #include "vector" 3 #include "set" 4 #include "map" 5 #include "stack" 6 #include "string" 7 #include "algorithm" 8 #include "iterator" 9 using namespace std;10 #define ALL(x) x.begin(),x.end()//宏11 #define INS(x) inserter(x,x.begin())//宏12 typedef set 
     
       Set;13 map
      
        IDcache;//集合映射成ID14 vector
       
         Setcache;//根据ID取集合15 int ID(Set x)//查找集合x的ID，找不到分配新的16 {17     if (IDcache.count(x))18         return IDcache[x];19     Setcache.push_back(x);//添加新集合20     return IDcache[x] = Setcache.size() - 1;21 }22 int main()23 {24     stack
        
          s;25     int m;26     cin >> m;27     while (m--)28     {29         int n;30         cin >> n;31         for (int i = 0; i < n; i++)32         {33             string op;34             cin >> op;35             if (op[0] == 'P')//PUSH36                 s.push(ID(Set()));//空集入栈37             else38                 if (op[0] == 'D')//DUP,栈顶复制一次再入栈39                     s.push(s.top());40                 else41                 {42                     Set x1 = Setcache[s.top()];43                     s.pop();44                     Set x2 = Setcache[s.top()];45                     s.pop();//出栈两个集合46                     Set x;47                     if (op[0] == 'U')//出栈两个集合，并集入栈48                         set_union(ALL(x1), ALL(x2), INS(x));49                     //获得两个集合的并集。两个输入序列须保证已排好序50                     if (op[0] == 'I')//出栈两个集合，交集入栈51                         set_intersection(ALL(x1), ALL(x2), INS(x));52                     if (op[0] == 'A')//出栈两个集合，先出栈的集合加到53                     {    //后出栈的集合中，再入栈54                         x = x2;55                         x.insert(ID(x1));56                     }57                     s.push(ID(x));58                 }59             cout << Setcache[s.top()].size() << endl;60         }61         //if (m != 0)62             cout << "***" << endl;63     }64     return 0;65 }