csp 202303-3 LDAP（模拟）

  关键：前缀表达式，选择合适的数据结构存储信息，避免TL

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int n, m;
unordered_map<int, unordered_map<int, set<int>>> book;每个属性key为val的DN的集合
unordered_map<int, set<int>> ve; //每个属性key不为N/A的DN的集合
stack<set<int> > st; //前缀表达式
string str;
set<int> solve(string s) //处理原子表达式
{
    int key, val, flag;
    set<int> se;
    for(int i = 0; i < str.size(); i++)
    {
        if(!isdigit(s[i]))
        {
            if(s[i] == ':')
                flag = 1;
            else
                flag = 0;
            key = stoi(s.substr(0, i));
            val = stoi(s.substr(i + 1));
            break;
        }
    }
    if(flag)  //“：”
    {
        se.insert(book[key][val].begin(), book[key][val].end());
    }
    else //“~”
    {
        se.insert(ve[key].begin(), ve[key].end());
        for(auto it: book[key][val])
        {
            if(se.count(it))
                se.erase(it);
        }
    }
    return se;
}
 
int main()
{
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin >> n;
    for(int i = 0; i < n; i++)
    {
        int id, cnt, key, val;
        cin >> id >> cnt;
        for(int j = 0; j < cnt; j++)
        {
            cin >> key >> val;
            book[key][val].insert(id);
            ve[key].insert(id);
        }
    }
    cin >> m;
    while(m--)
    {
        cin >> str;
        for(int i = str.size() - 1; i >= 0; i--)
        {
            if(isdigit(str[i]))
            {
                string s = "";
                int j;
                for(j = i; j >= 0; j--)
                {
                    if(str[j] == '(' || str[j] == ')')
                        break;
                    s += str[j];
                }
                reverse(s.begin(), s.end());
                i = j;
 
                st.push(solve(s));
            }
            else if(str[i] == '&')
            {
                set<int> s1 = st.top();
                st.pop();
                set<int> s2 = st.top();
                st.pop();
                set<int> s3;
                for(auto it : s1)
                {
                    if(s2.count(it))
                        s3.insert(it);
                }
                st.push(s3);
            }
            else if(str[i] == '|')
            {
                set<int> s1 = st.top();
                st.pop();
                set<int> s2 = st.top();
                st.pop();
                set<int> s3;
                s3.insert(s1.begin(), s1.end());
                s3.insert(s2.begin(), s2.end());
                st.push(s3);
            }
        }
        set<int> se = st.top();
        for(auto it : se)
            cout << it << " ";
        cout << endl;
    }
 
    return 0;
}