Background from Wikipedia: \Set theory is abranch of mathematics created principally by theGerman mathematician Georg Cantor at the end ofthe 19th century. Initially controversial, set theoryhas come to play the role of a foundational theoryin modern mathematics, in the sense of a theoryinvoked to justify assumptions made in mathemat-ics concerning the existence of mathematical objects(such as numbers or functions) and their properties.Formal versions of set theory also have a founda-tional role to play as specifying a theoretical idealof mathematical rigor in proofs."Given this importance of sets, being the basis of mathematics, a set of eccentric theorist set off toconstruct a supercomputer operating on sets instead of numbers. The initial SetStack Alpha is underconstruction, and they need you to simulate it in order to verify the operation of the prototype.The computer operates on a single stack of sets, which is initially empty. After each operation, thecardinality of the topmost set on the stack is output. The cardinality of a setSis denotedjSjand is thenumber of elements inS. The instruction set of the SetStack Alpha isPUSH,DUP,UNION,INTERSECT,andADD.PUSHwill push the empty setfgon the stack.DUPwill duplicate the topmost set (pop the stack, and then push that set on the stack twice).UNIONwill pop the stack twice and then push the union of the two sets on the stack.INTERSECTwill pop the stack twice and then push the intersection of the two sets on the stack.ADDwill pop the stack twice, add the rst set to the second one, and then push the resulting seton the stack.For illustration purposes, assume that the topmost element of the stack isA=ffg;ffgggand that the next one isB=ffg;fffggggFor these sets, we havejAj= 2 andjBj= 2. Then:UNIONwould result in the setffg,ffgg,fffgggg. The output is 3.INTERSECTwould result in the setffgg. The output is 1.ADDwould result in the setffg,fffggg,ffg,ffgggg. The output is 3.InputAn integer 0T5 on the rst line gives the cardinality of the set of test cases. The rst line of eachtest case contains the number of operations 0N2000. Then followNlines each containing one ofthe ve commands. It is guaranteed that the SetStack computer can execute all the commands in thesequence without ever popping an empty stack.OutputFor each operation specied in the input, there will be one line of output consisting of a single integer.This integer is the cardinality of the topmost element of the stack after the corresponding commandhas executed. After each test case there will be a line with `***‘ (three asterisks).SampleInput29PUSHDUPADDPUSHADDDUPADDDUPUNION5PUSHPUSHADDPUSHINTERSECTSampleOutput001011222***00100***

  1 #include <iostream>  2 #include <cstdio>  3 #include <cstring>  4 #include <algorithm>  5 #include <cmath>  6 #include <string>  7 #include <vector>  8 #include <set>  9 #include <map> 10 #include <queue> 11 #include <stack> 12 #include <sstream> 13 #include <cctype> 14 using namespace std; 15 const int INF = 0x7fffffff; 16 const double EXP = 1e-8; 17 const int MS = 105; 18 typedef long long LL; 19 int id; 20 typedef set<int> SET; 21 map<SET, int>  mp; 22 typedef set<int>::iterator IT; 23 stack<SET> sta; 24 void ID(SET s) 25 { 26     if (mp.count(s)) 27         return; 28     mp[s] = id++; 29 } 30  31 void PUSH() 32 { 33     SET S; 34     ID(S); 35     sta.push(S); 36 } 37  38 void DUP() 39 { 40     sta.push(sta.top()); 41 } 42  43 void UNION() 44 { 45     SET S, S2; 46     S2 = sta.top(); 47     sta.pop(); 48     S = sta.top(); 49     sta.pop(); 50     for (IT it = S2.begin(); it != S2.end(); it++) 51         S.insert(*it); 52     ID(S); 53     sta.push(S); 54 } 55  56 void INTERSECT() 57 { 58     SET S, S2, S3; 59     S2 = sta.top(); 60     sta.pop(); 61     S3 = sta.top(); 62     sta.pop(); 63     for (IT it = S2.begin(); it != S2.end(); it++) 64     { 65         if (S3.count(*it)) 66             S.insert(*it); 67     } 68     ID(S); 69     sta.push(S); 70 } 71  72 void ADD() 73 { 74     SET S1, S2; 75     S1 = sta.top(); 76     sta.pop(); 77     S2 = sta.top(); 78     sta.pop(); 79     S2.insert(mp[S1]); 80     ID(S2); 81     sta.push(S2); 82 } 83  84 void TOPSIZE() 85 { 86     cout << sta.top().size() << endl; 87 } 88 void solve() 89 { 90     char op[10]; 91     cin >> op; 92     switch (op[0]) 93     { 94     case ‘P‘:PUSH(); break; 95     case ‘D‘:DUP(); break; 96     case ‘U‘:UNION(); break; 97     case ‘I‘:INTERSECT(); break; 98     case ‘A‘:ADD(); break; 99     }100     TOPSIZE();101 }102 int main()103 {104     int T;105     cin >> T;106     while (T--)107     {108         int n;109         cin >> n;110         mp.clear();111         while (!sta.empty())112             sta.pop();113         id = 0;114         while (n--)115             solve();116         cout << "***" << endl;117     }118     return 0;119 }