# 11218: 【原1218】settest

### 题目描述

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

## 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
``````

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;
}
}
}
}

//复制
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;
}
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;
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) {
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) {
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;
}
``````