问题

有一个专门为了集合运算而设计的“集合栈”计算机。该机器有一个初始为空的栈，并且支持以下操作：

PUSH：空集“{}”入栈

DUP：把当前栈顶元素复制一份后再入栈

UNION：出栈两个集合，然后把两者的并集入栈

INTERSECT：出栈两个集合，然后把二者的交集入栈

ADD：出栈两个集合，然后把先出栈的集合加入到后出栈的集合中，把结果入栈

每次操作后，输出栈顶集合的大小（即元素个数）。例如栈顶元素是A={ {}， {{}} }， 下一个元素是B={ {}， {{{}}} }，则：<br />UNION操作将得到{ {}， {{}}， {{{}}} }，输出3.

INTERSECT操作将得到{ {} }，输出1

ADD操作将得到{ {}， {{{}}}， { {}， {{}} } }，输出3.

输入不超过2000个操作

Sample Input

9
PUSH
DUP
ADD
PUSH
ADD
DUP
ADD
DUP
UNION

Sample Output

0
0
1
0
1
1
2
2
2

题解

首先可以确定要用到数据结构栈，然后观察这个栈的特点： 存放的是集合，而集合里面存放的也是集合。

所以这个栈的结构应该是这样的: stack<set<set<>,set<>>,set<>>

然而，这种结构明显是不科学的，它像一个无穷递归一样，永无止境。

观察到，栈只是用来存放集合的地方，而集合的操作与栈没有关联。

于是我们可以把地址和数据分离：将集合映射为“地址”(即整数ID)，每次取出(即与位置有关)通过ID访问集合，再对集合单独操作。

这让我们要用两种映射：

• 从集合映射到ID：map<set<int>,int> idData // 存放地址
• 从ID映射到集合：map<int,set<int>> setData // 存放数据
  然而ID符合0~n，所以可以用vector<set<int>>实现。

这也是模拟链表的思想。

代码

/*
栈 模拟链表 
*/
#include <bits/stdc++.h>
#define ALL(x) x.begin(),x.end()
#define INS(x) inserter(x,x.begin())
using namespace std;
typedef set<int> Set;
map<Set,int> idData;
vector<Set> setData;// map<int,Set> SetData
int ID(Set x)
{
    if(idData.count(x)) return idData[x];
    setData.push_back(x);
    return idData[x] = setData.size() - 1;
}
int main()
{
    int n,m;
    char ord[100];
    scanf("%d",&n);
    while(n--)
    {
        scanf("%d",&m);
        stack<int> st;
        while(m--)
        {
            scanf("%s",&ord);
            if(ord[0] == 'P') st.push(ID(Set()));
            else if(ord[0] == 'D') st.push(st.top());
            else
            {
                Set x1 = setData[st.top()];
                st.pop();
                Set x2 = setData[st.top()];
                st.pop();
                Set x;
                if(ord[0] == 'U') set_union(ALL(x1),ALL(x2),INS(x));
                else if(ord[0] == 'I') set_intersection(ALL(x1),ALL(x2),INS(x));
                else if(ord[0] == 'A')
                {
                    x = x2;
                    x.insert(ID(x1));
                }
                st.push(ID(x));
            }
            printf("%d\n",setData[st.top()].size());
        }
        printf("***\n");
    }
    return 0;
}