11218: 【原1218】settest

题目

题目描述

author: DS TA 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1218

Description

初始有一空集，然后对这个集合共有 n 次操作，每次给定一个集合以及操作名称（并: + / 差: - / 交: *）。每个操作完成后输出当前集合所有元素（均为整数，从小到大输出）。

Input Format

第 1 行: 一个数, n

第 2..(n + 1) 行: 每行首先一个字符 c （+/-/*），表示当前操作名称.

接下来一个整数 m，表示给定的集合元素个数.

接下来 m 个整数，给定这个集合里所有元素。

Output Format

输出共 n 行: 每行按照元素从小到大的顺序输出在执行完当前操作后你手上集合的所有元素。

Sample Input:

7
+ 3 1 2 3
- 1 2
+ 3 4 5 6
* 2 1 4
- 2 1 4
+ 1 100
- 1 99

Sample Output:

1 2 3
1 3
1 3 4 5 6
1 4

100
100

Limits

n, m <= 100

ligongzzz's solution

#include "iostream"
using namespace std;


//红黑树实现
template <class T>
class mSet {
    //颜色枚举类型
    enum colorT { RED, BLACK };

    //结点
    class node {
    public:
        T* data;
        node* lchild = nullptr;
        node* rchild = nullptr;
        node* parent = nullptr;

        colorT color = RED;
    };

    //根节点
    node* root = nullptr;

    //清空
    void clear(node* p) {
        if (p != nullptr) {
            clear(p->lchild);
            clear(p->rchild);
            delete p->data;
            delete p;
        }
        p = nullptr;
    }

    //旋转
    //LL旋转
    void LL(node* gp) {
        auto p = gp->lchild, t = p->lchild;
        if (gp->parent != nullptr) {
            if (gp->parent->lchild == gp)
                gp->parent->lchild = p;
            else
                gp->parent->rchild = p;
        }
        else
            root = p;
        p->parent = gp->parent;
        gp->lchild = p->rchild;
        if (p->rchild != nullptr)
            p->rchild->parent = gp;
        p->rchild = gp;
        gp->parent = p;
        //修改颜色
        auto tmp = gp->color;
        gp->color = p->color;
        p->color = tmp;
        //cout << "LL ";
    }

    //RR旋转
    void RR(node * gp) {
        auto p = gp->rchild, t = p->rchild;
        if (gp->parent != nullptr) {
            if (gp->parent->lchild == gp)
                gp->parent->lchild = p;
            else
                gp->parent->rchild = p;
        }
        else
            root = p;
        p->parent = gp->parent;
        gp->rchild = p->lchild;
        if (p->lchild != nullptr)
            p->lchild->parent = gp;
        p->lchild = gp;
        gp->parent = p;
        //修改颜色
        auto tmp = gp->color;
        gp->color = p->color;
        p->color = tmp;
        //cout << "RR ";
    }

    //LR旋转
    void LR(node * gp) {
        RR(gp->lchild);
        LL(gp);
        //cout << "LR ";
    }

    //RL旋转
    void RL(node * gp) {
        LL(gp->rchild);
        RR(gp);
        //cout << "RL ";
    }

    //插入调整
    void insertAdjust(node * &gp, node * &p, node * t) {
        if (p->color == BLACK) return;
        if (p == root) {
            p->color = BLACK;
            return;
        }
        if (gp->lchild == p) {
            if (p->lchild == t) {
                LL(gp);
                //交换次序
                auto tmp = gp;
                gp = p;
                p = tmp;

            }
            else {
                LR(gp);
                //交换次序
                auto tmp = gp;
                gp = t;
                t = tmp;
            }
        }
        else if (p->rchild == t) {
            RR(gp);
            //交换次序
            auto tmp = gp;
            gp = p;
            p = tmp;
        }
        else {
            RL(gp);
            //交换次序
            auto tmp = gp;
            gp = t;
            t = tmp;
        }
    }

    //删除调整
    void removeAdjust(node*& p, node*& c, node*& t, const T& del) {
        if (c->color == RED) return;
        if (c == root)
            if (c->lchild && c->rchild
                && c->rchild->color == c->lchild->color) {
                c->color = RED;
                c->lchild->color = c->rchild->color = BLACK;
                return;
            }
        if ((c->lchild && c->lchild->color || c->lchild == nullptr) &&
            (c->rchild && c->rchild->color || c->rchild == nullptr))
            if ((t->lchild && t->lchild->color || t->lchild == nullptr) &&
                (t->rchild && t->rchild->color || t->rchild == nullptr)) {
                p->color = BLACK;
                t->color = c->color = RED;
            }
            else {
                if (p->lchild == t)
                    if (t->lchild != nullptr && t->lchild->color == RED) {
                        t->lchild->color = BLACK;
                        LL(p);
                        //交换次序
                        t = p;
                    }
                    else {
                        auto tmp = t->rchild;
                        LR(p);
                        p = tmp;
                        p = p->rchild;
                        p->color = BLACK;
                        t->color = BLACK;
                    }
                else if (t->rchild&& t->rchild->color == RED) {
                    t->rchild->color = BLACK;
                    RR(p);
                    t = p;
                }
                else {
                    auto tmp = t->lchild;
                    RL(p);
                    p = tmp;
                    p = p->lchild;
                    p->color = BLACK;
                    t->color = BLACK;
                }
                c->color = RED;
            }
        else {
            if (*c->data == del) {
                if (c->lchild && c->rchild) {
                    if (c->rchild->color == BLACK) {
                        LL(c);
                    }
                    return;
                }
                if (c->lchild) {
                    LL(c);
                    p = c->parent;
                }
                else {
                    RR(c);
                    p = c->parent;
                }
            }
            else {
                p = c;
                c = del < *p->data ? p->lchild : p->rchild;
                t = c == p->lchild ? p->rchild : p->lchild;
                if (c->color == BLACK) {
                    if (t == p->rchild)
                        RR(p);
                    else
                        LL(p);
                    t = p;
                    t = c == p->lchild ? p->rchild : p->lchild;
                    removeAdjust(p, c, t, del);
                }
            }
        }
    }

    //复制
    void copy(node * posDes, node * posSource) {
        posDes->data = new T(*posSource->data);
        posDes->color = posSource->color;
        if (posSource->lchild) {
            posDes->lchild = new node;
            posDes->lchild->parent = posDes;
            copy(posDes->lchild, posSource->lchild);
        }
        if (posSource->rchild) {
            posDes->rchild = new node;
            posDes->rchild->parent = posDes;
            copy(posDes->rchild, posSource->rchild);
        }
    }

public:
    //迭代器（测试模块）
    class iterator {
        node* currentData = nullptr;
        friend iterator mSet::begin();
        friend iterator mSet::find(const T&);
        friend void mSet::erase(const iterator&);

    public:
        iterator() = default;

        iterator(const iterator& b) {
            currentData = new node;
            currentData = b.currentData;
        }

        T& get() {
            return *currentData->data;
        }
        //遍历结束或内容为空
        bool finish() {
            return currentData == nullptr;
        }

        //重载++i
        iterator& operator++() {
            if (currentData == nullptr)
                return *this;
            //假如有右孩子
            if (currentData->rchild != nullptr) {
                for (currentData = currentData->rchild; currentData->lchild != nullptr;)
                    currentData = currentData->lchild;
            }
            //假如是落单的根节点
            else if (currentData->parent == nullptr) {
                currentData = nullptr;
            }
            //假如是左叶子
            else if (currentData->parent->lchild == currentData)
                currentData = currentData->parent;
            //假如是右叶子
            else {
                auto last = currentData;
                for (currentData = currentData->parent;
                    currentData != nullptr && currentData->rchild == last;
                    currentData = currentData->parent)
                    last = currentData;
            }
            return *this;
        }

        //重载i++
        iterator operator++(int) {
            auto temp = *this;
            if (currentData == nullptr)
                return temp;
            //假如有右孩子
            if (currentData->rchild != nullptr) {
                for (currentData = currentData->rchild; currentData->lchild != nullptr;)
                    currentData = currentData->lchild;
            }
            //假如是落单的根节点
            else if (currentData->parent == nullptr) {
                currentData = nullptr;
            }
            //假如是左叶子
            else if (currentData->parent->lchild == currentData)
                currentData = currentData->parent;
            //假如是右叶子
            else {
                auto last = currentData;
                for (currentData = currentData->parent;
                    currentData != nullptr && currentData->rchild == last;
                    currentData = currentData->parent)
                    last = currentData;
            }
            return temp;
        }

        //重载取值符号
        T& operator*() const {
            if (currentData == nullptr)
                return *new T;
            else
                return *currentData->data;
        }

        //重载==符号
        bool operator==(const iterator & b) const {
            return currentData == b.currentData;
        }

        //重载!=符号
        bool operator!=(const iterator & b) const {
            return currentData != b.currentData;
        }
    };

    //查找
    iterator find(const T & num) {
        iterator ans;
        auto p = root;
        while (p != nullptr && *p->data != num)
            if (*p->data > num)
                p = p->lchild;
            else
                p = p->rchild;

        ans.currentData = p;
        return ans;
    }

    //清空
    void clear() {
        clear(root);
    }

    //插入
    void insert(const T & x) {
        node* t, * parent, * grandp;

        //在空树上插入
        if (root == nullptr) {
            root = new node;
            root->color = BLACK;
            root->data = new T(x);
            return;
        }

        parent = grandp = t = root;
        while (true) {
            if (t != nullptr) {
                if (t->lchild&& t->lchild->color == RED &&
                    t->rchild && t->rchild->color == RED) {
                    t->lchild->color = t->rchild->color = BLACK;
                    t->color = RED;
                    insertAdjust(grandp, parent, t);
                }
                grandp = parent;
                parent = t;
                t = *t->data > x ? t->lchild : t->rchild;
            }
            else {
                t = new node;
                t->data = new T(x);
                t->parent = parent;
                if (x < *parent->data)
                    parent->lchild = t;
                else
                    parent->rchild = t;
                insertAdjust(grandp, parent, t);
                root->color = BLACK;
                return;
            }
        }
    }

    //查找删除
    void remove(const T & x) {
        T del = x;
        node* t, * p, * c;

        if (root == nullptr) return;
        if (*root->data == x && root->lchild == nullptr && root->rchild == nullptr) {
            delete root;
            root = nullptr;
            return;
        }

        p = c = t = root;
        while (true) {
            removeAdjust(p, c, t, del);
            if (*c->data == del && c->lchild && c->rchild) {
                auto tmp = c->rchild;
                while (tmp->lchild)
                    tmp = tmp->lchild;
                c->data = tmp->data;
                del = *tmp->data;
                p = c;
                c = c->rchild;
                t = p->lchild;
                continue;
            }

            if (*c->data == del) {
                if (p->lchild == c)
                    p->lchild = nullptr;
                else
                    p->rchild = nullptr;
                delete c;
                root->color = BLACK;
                return;
            }
            p = c;
            c = del < *p->data ? p->lchild : p->rchild;
            t = c == p->lchild ? p->rchild : p->lchild;
        }
    }

    //迭代器擦除
    void erase(const iterator & x) {
        //判断是否为空
        if (x.currentData == nullptr)
            return;

        T * del = x.currentData->data;
        node * t, *p, *c;

        if (root == nullptr) return;
        if (root->data == del && root->lchild == nullptr && root->rchild == nullptr) {
            delete root;
            root = nullptr;
            return;
        }

        p = c = t = root;
        while (true) {
            removeAdjust(p, c, t, *del);
            if (c->data == del && c->lchild && c->rchild) {
                auto tmp = c->rchild;
                while (tmp->lchild)
                    tmp = tmp->lchild;
                if (tmp->parent != c) {
                    auto temp = *tmp;
                    tmp->parent = c->parent;
                    if (tmp->parent)
                        if (tmp->parent->lchild == c)
                            tmp->parent->lchild = tmp;
                        else tmp->parent->rchild = tmp;
                    else root = tmp;
                    tmp->lchild = c->lchild;
                    if (c->lchild) c->lchild->parent = tmp;
                    tmp->rchild = c->rchild;
                    if (c->rchild) c->rchild->parent = tmp;
                    tmp->color = c->color;

                    c->parent = temp.parent;
                    if (temp.parent->lchild == tmp)
                        temp.parent->lchild = c;
                    else temp.parent->rchild = c;
                    c->lchild = temp.lchild;
                    if (c->lchild) c->lchild->parent = c;
                    c->rchild = temp.rchild;
                    if (c->rchild) c->rchild->parent = c;
                    c->color = temp.color;
                }
                else {
                    auto temp = *tmp;
                    tmp->parent = c->parent;
                    if (tmp->parent)
                        if (tmp->parent->lchild == c)
                            tmp->parent->lchild = tmp;
                        else tmp->parent->rchild = tmp;
                    else root = tmp;
                    if (c->lchild == tmp) {
                        tmp->lchild = c;
                        tmp->rchild = c->rchild;
                        if (c->rchild) tmp->rchild->parent = tmp;
                    }
                    else {
                        tmp->rchild = c;
                        tmp->lchild = c->lchild;
                        if (c->lchild) tmp->lchild->parent = tmp;
                    }
                    c->parent = tmp;
                    c->lchild = temp.lchild;
                    c->rchild = temp.rchild;
                    if (c->lchild) c->lchild->parent = c;
                    if (c->rchild) c->rchild->parent = c;
                    tmp->color = c->color;
                    c->color = temp.color;
                }

                p = c = tmp;
                c = c->rchild;
                t = p->lchild;
                continue;
            }

            if (c->data == del) {
                if (p->lchild == c)
                    p->lchild = nullptr;
                else
                    p->rchild = nullptr;
                delete c;
                root->color = BLACK;
                return;
            }
            p = c;
            c = *del < *p->data ? p->lchild : p->rchild;
            t = c == p->lchild ? p->rchild : p->lchild;
        }
    }

    void erase(const iterator & from, const iterator & to) {
        if (from == end()) return;
        for (auto p = from; p != to;)
            erase(p++);
    }

    //迭代器起始
    iterator begin() {
        iterator result;
        auto p = root;
        if (p != nullptr)
            for (; p->lchild != nullptr;) {
                p = p->lchild;
            }
        result.currentData = p;
        return result;
    }

    //迭代器结束
    iterator end() {
        return *new iterator;
    }

    //重载赋值符号
    mSet<T> operator=(const mSet<T> & b) {
        clear();
        root = nullptr;
        if (b.root == nullptr) 
            return *this;
        root = new node;
        copy(root, b.root);
        return *this;
    }

    //检查是否合法
    int check(node* pos) {
        int left=0,right=0;
        if (pos->lchild != nullptr)
            left = check(pos->lchild);
        if (pos->rchild != nullptr)
            right = check(pos->rchild);
        if (left < 0 || right < 0 || left != right)
            return -1;
        if (pos->color == BLACK)
            return 1 + left;
        else return left;
    }

    void check() {
        if (root == nullptr || check(root) > 0)
            cout << "检查合格！" << endl;
        else 
            cout << "检查不合格！" << endl;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    mSet<int> setData;
    int num;
    cin >> num;

    for (; num > 0; num--) {
        char c;
        int n;

        cin >> c >> n;

        if (c=='+') {
            for (; n > 0; n--) {
                int temp;
                cin >> temp;
                if (setData.find(temp) == setData.end())
                    setData.insert(temp);
            }
        }
        else if (c=='-') {
            for (; n > 0; n--) {
                int temp;
                cin >> temp;
                setData.erase(setData.find(temp));
            }
        }
        else {
            mSet<int> newSet;
            for (; n > 0; n--) {
                int temp;
                cin >> temp;
                if (setData.find(temp) != setData.end() && newSet.find(temp) == newSet.end())
                    newSet.insert(temp);
            }
            setData = newSet;
        }

        bool first = true;
        for (auto p : setData)
            if (!first)
                cout << " " << p;
            else {
                first = false;
                cout << p;
            }
        cout << endl;
    }

    return 0;
}

Neight99's solution

#include <iostream>

using namespace std;

const int maxN = 1e5 + 100;
int lists[maxN] = {0}, length = 0;

void qSort(int *, int, int);
bool find(int);
int search(int, int *, int, int);

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int N, M, tmp;
    char order;
    cin >> N;

    for (int i = 0; i < N; i++) {
        cin >> order >> M;

        if (order == '+') {
            for (int j = 0; j < M; j++) {
                cin >> tmp;
                if (find(tmp)) {
                    lists[length] = tmp;
                    length++;
                }
            }
            qSort(lists, 0, length - 1);
        } else if (order == '-') {
            bool isHere[maxN];
            for (int j = 0; j < length + 10; j++) {
                isHere[j] = 1;
            }

            int listsTmp[maxN] = {0};
            for (int j = 0; j < M; j++) {
                cin >> tmp;
                int pos = search(tmp, lists, 0, length - 1);
                if (pos != -1) {
                    isHere[pos] = 0;
                }
            }
            int lengthTmp = length, pos = 0;
            for (int j = 0; j < lengthTmp; j++) {
                if (!isHere[j]) {
                    length--;
                    continue;
                } else {
                    listsTmp[pos] = lists[j];
                    pos++;
                }
            }

            for (int j = 0; j < length; j++) {
                lists[j] = listsTmp[j];
            }
        } else if (order == '*') {
            bool isHere[maxN] = {0};
            int listsTmp[maxN] = {0};
            for (int j = 0; j < M; j++) {
                cin >> tmp;
                int pos = search(tmp, lists, 0, length - 1);
                if (pos != -1) {
                    isHere[pos] = 1;
                }
            }
            int lengthTmp = length, pos = 0;
            for (int j = 0; j < lengthTmp; j++) {
                if (!isHere[j]) {
                    length--;
                    continue;
                } else {
                    listsTmp[pos] = lists[j];
                    pos++;
                }
            }
            for (int j = 0; j < length; j++) {
                lists[j] = listsTmp[j];
            }
        }

        for (int j = 0; j < length; j++) {
            cout << lists[j] << ' ';
        }
        cout << '\n';
    }

    return 0;
}

void qSort(int *nums, int l, int h) {
    if (l >= h) {
        return;
    }
    int first = l, last = h;
    int key = nums[first];

    while (first < last) {
        while (first < last && nums[last] >= key) {
            --last;
        }
        nums[first] = nums[last];
        while (first < last && nums[first] <= key) {
            ++first;
        }
        nums[last] = nums[first];
    }
    nums[first] = key;
    qSort(nums, l, first - 1);
    qSort(nums, first + 1, h);
}

bool find(int x) {
    for (int i = 0; i < length; i++) {
        if (x == lists[i]) {
            return 0;
        }
    }
    return 1;
}

int search(int x, int *nums, int l, int h) {
    if (l > h) {
        return -1;
    }
    int mid = (l + h) / 2;
    if (nums[mid] == x) {
        return mid;
    } else if (nums[mid] < x) {
        return search(x, nums, mid + 1, h);
    } else if (nums[mid] > x) {
        return search(x, nums, l, mid - 1);
    }

    return -1;
}

yyong119's solution

#include <iostream>
using namespace std;

int mid(int a, int b, int c) {
    if (a < b) {
        if (b < c)return b;
        else if (c < a) return a;
        else return c;
    }
    else {
        if (a < c) return a;
        else if (c < b) return b;
        else return c;
    }
}

void partition(int arr[], int begin, int end, int& newEnd, int& newBegin) {
    int pivot = mid(arr[begin], arr[end], arr[(begin + end) / 2]);
    int pos = begin;
    while (pos <= end)
        if (arr[pos] < pivot) {
            int tmp = arr[pos];
            arr[pos++] = arr[begin];
            arr[begin++] = tmp;
        }
        else if (arr[pos] > pivot) {
            int tmp = arr[pos];
            arr[pos] = arr[end];
            arr[end--] = tmp;
        }
        else ++pos;
    newEnd = begin - 1;
    newBegin = end + 1;
}

void quick_sort(int arr[], int begin, int end) {
    if (begin < end) {
        int newEnd, newBegin;
        partition(arr, begin, end, newEnd, newBegin);
        quick_sort(arr, begin, newEnd);
        quick_sort(arr, newBegin, end);
    }
}

class set {
    friend istream& operator >> (istream &is, set& s) {
        for (int i = 0; i < s.size; ++i)
            is >> s.data[i];
        return is;
    }
    friend ostream& operator<<(ostream &os, const set& s) {
        for (int i = 0; i < s.size; ++i) os << s.data[i] << ' ';
        return os;
    }
private:
    int *data;
    int size;
    int maxSize;

    int find(int n) const {
        int l = 0, r = size - 1;
        while (l <= r) {
            if (data[l] >= n) break;
            int mid = (l + r) / 2;
            if (data[mid] < n)l = mid + 1;
            else r = mid;
        }
        return l;
    }
public:
    set(int sz, int cp = 10000) :size(sz), maxSize(cp) { data = new int[maxSize]; }
    ~set() { delete[]data; }
    void operator+(const set& other) {
        for (int i = 0; i < other.size; ++i) {
            int pos = find(other.data[i]);
            if (pos == size)data[size++] = other.data[i];
            else if (data[pos] > other.data[i]) {
                for (int j = size++; j > pos; --j) data[j] = data[j - 1];
                data[pos] = other.data[i];
            }
        }
    }
    void operator-(const set& other) {
        for (int i = 0; i < other.size; ++i) {
            int pos = find(other.data[i]);
            if (pos < size&&data[pos] == other.data[i]) {
                for (int j = pos; j < size - 1; ++j) data[j] = data[j + 1];
                --size;
            }
        }
    }
    void operator*(const set& other) {
        int *tmp = new int[maxSize];
        int cnt = 0;
        int i, j;
        quick_sort(other.data, 0, other.size - 1);
        if (other.size > 0) i = find(other.data[0]);
        for (j = 0; j < other.size; ++j) {
            for (; i < size; ++i)
                if (data[i] >= other.data[j]) break;
            if (i == size) break;
            else if (data[i] == other.data[j]) tmp[cnt++] = data[i];
        }
        delete[]data;
        data = tmp;
        size = cnt;
    }
};

int main() {

    ios::sync_with_stdio(false);
    int n; cin >> n;
    set s(0);
    int m; char c;
    for (int i = 0; i < n; ++i) {
        cin >> c >> m;
        set s2(m);
        cin >> s2;
        switch (c) {
            case '+':
                s + s2;
                cout << s << '\n';
                break;
            case '-':
                s - s2;
                cout << s << '\n';
                break;
            case '*':
                s * s2;
                cout << s << '\n';
        }
    }
    return 0;
}

Zsi-r's solution

#include <iostream>

using namespace std;

class set
{
    friend istream &operator>>(istream &is, set &x)
    {
        for (int i = 0; i < x.max; i++)
            is >> x.array[i];
        x.current_length = x.max;
        x.sort(x.array);
        return is;
    }
    friend ostream &operator<<(ostream&os,const set &x)
    {
        for (int i =0;i<x.current_length;i++)
            os << x.array[i]<<' ';
        return os;
    }
public:
    int max;
    int current_length;
    int *array;

    set(int n)
    {
        max = n;
        current_length = 0;
        array = new int[max];
    }
    ~set() { delete[] array; }

    void sort(int x[])
    {
        mergeSort(x, 0, current_length-1);
    }
    void mergeSort(int a[],int left ,int right);
    void merge(int a[],int left,int mid,int right);
    void plus(set &x);
    void minus(set &x);
    void intersection(set &x);
};

void set::merge(int a[],int left,int mid,int right)
{
    int *tmp = new int [right-left+1];

    int i=left,j =mid,k =0;

    while (i < mid && j <= right) {
      if (a[i] < a[j])
        tmp[k++] = a[i++];
      else
        tmp[k++] = a[j++];
    }

    while (i < mid)
      tmp[k++] = a[i++];
    while (j <= right) tmp[k++] = a[j++];

    for (i =0,k=left;k<=right;)a[k++] = tmp[i++];
    delete []tmp;
}

void set::mergeSort(int a[], int left, int right)
{
    int mid = (left+right)/2;

    if (left == right) return ;
    mergeSort(a, left, mid);
    mergeSort(a, mid+1, right);
    merge(a,left,mid+1,right);
}

void set::plus(set &x)
{
    set temp(x.current_length + current_length);
    int num1, num2, i = 0, j = 0;

    while (i < x.current_length && j < current_length)
    {
        num1 = x.array[i];
        num2 = array[j];
        if (num1 < num2)
        {
            temp.array[temp.current_length++] = num1;
            i++;
        }
        else if (num2 < num1)
        {
            temp.array[temp.current_length++] = num2;
            j++;
        }
        else if (num2 == num1)
        {
            temp.array[temp.current_length++] = num1;
            i++;
            j++;
        }
    }
    while (i < x.current_length)
    {
        temp.array[temp.current_length++] = x.array[i++];
    }
    while (j < current_length)
    {
        temp.array[temp.current_length++] = array[j++];
    }

    delete[] array;
    max = temp.current_length;
    current_length = 0;
    array = new int[max];
    for (; current_length < temp.current_length; current_length++)
    {
        array[current_length] = temp.array[current_length];
    }
}

void set::minus(set &x)
{
    int size = (current_length > x.current_length) ? current_length : x.current_length;
    set temp(size);

    int i = 0, j = 0;
    while (i < current_length && j < x.current_length)
    {
        if (array[i] < x.array[j])
            temp.array[temp.current_length++] = array[i++];
        else if (array[i] == x.array[j])
        {
            i++;
            j++;
        }
        else if(array[i]>x.array[j])
            j++;
    }
    while(i<current_length)temp.array[temp.current_length++] = array[i++];

    delete[]array;
    max = temp.current_length;
    array = new int [max];
    current_length = 0;
    for (;current_length<temp.current_length;current_length++)
    {
        array[current_length] = temp.array[current_length];
    }
}

void set::intersection(set&x)
{
    int size = (current_length > x.current_length) ? current_length : x.current_length;
    set temp(size);

    int i=0,j=0;
    while(i<current_length&&j<x.current_length)
    {   
        if (array[i]==x.array[j]){
            temp.array[temp.current_length++] = array[i];
            i++;
            j++;
        }
        else if (array[i]<x.array[j]) i++;
        else if (array[i]>x.array[j]) j++;
    }

    delete []array;
    max = temp.current_length;
    array = new int[max];
    current_length = 0;
    for (;current_length<temp.current_length;current_length++)
    {
        array[current_length] = temp.array[current_length];
    }
}

int main()
{   
    int lines,numofelem;
    cin >> lines;
    char op;

    set set1(100);

    for (int i=0;i<lines;i++)
    {
        cin >>op;
        cin >>numofelem;
        set temp(numofelem);
        cin >> temp;
        if (op=='+')
            set1.plus(temp);
        else if (op=='-')
            set1.minus(temp);
        else if (op=='*')
            set1.intersection(temp);
        cout << set1 <<endl;
    }
    return 0;
}