Description

Tim Brown published a game “Rolling Balls”.
In this game, the player’s target is to roll balls with different colors into a moving bag as more as possible. A ball can be represented by its color (r, g, b).

Unfortunately, some unscrupulous players always want to cheat in the game.
Therefore, Tim hires you to make a cheating detection system CDSystem, which monitors and simulates the game progress to figure out any impossible data modification.

Your task is to complete a data structure called MultiSet, which can be implemented using Binary Search Tree as MultiSet_Tree.
In this problem, a MultiSet is used to represent a moving bag, into which balls with different colors can be rolled.

MultiSet

MultiSet is a data structure that supports the following operations:

1. Insert(x): insert an element x into the set
2. Delete(x): remove one element x from the set if there’re some x in the set
3. Search(x): return the amount of x in the set

Example:
The MultiSet MS={a,b,y,y}. Search(a) = 1, Search(y) = 2, Search(x) = 0.
After Insert(x) and Delete(y), MS={a,b,x,y}. Then, Search(y) = 1, Search(x) = 1.

MultiSet_Tree

MultiSet_Tree is MultiSet implemented using Binary Search Tree, where the tree nodes store the elements and their amounts in the set. The Insert and Delete operations of MultiSet_Tree can be further explained as follows:

• Insert(x): 

• Delete(x):

MultiSet_Tree Node Greatness/Smallness: Colors of Balls

In this problem, a MultiSet_Tree node represents a specific ball color (r, g, b).
To implement Binary Search Tree, the greatness/smallness (<, >, ==) between two colors is determined sequentially below:

1. Compare the r values of the two colors.
2. If the r values equal, compare the g values of the two colors.
3. If the g values equal, compare the b values of the two colors.
4. If all the r, g, b values are the same, the two colors are equal.

In this partial judge problem, you have to complete:

1. Color: operators <, >, ==, =, where the assignment operator = is needed when you make/modify MultiSet_Tree Nodes.
2. Node: Constructor, Destructor
3. MultiSet_Tree: Constructor, Destructor, Insert, Delete, Search

More Hints on Case 3 of MultiSet_Tree Delete Operation

Supposing Node x with amount ==1 is to be deleted, three possible sub-cases should be considered:

1. Node x has 2 children: replace x by the Node with the largest key among the keys less than x.
2. Node x has 1 child: replace x by its child Node
3. Node x has no child: replace x by NULL.
   
   

Input

The first line gives the number of test cases T.
Each case consists of one integer N and N lines of operations.

Each operation opi is with one of the following formats:

• "+ r g b": Roll a ball with color (r,g,b) into the bag.
• "- r g b": Take away a ball with color (r,g,b) from the bag. If there’s no such ball, just do nothing.
• "? r g b": Print the number of balls with color (r,g,b).
• "PrintSet": Print all nodes (key, amount, level) of MultiSet_Tree in the level-order traversal, where the key is color (r, g, b).

It’s guaranteed that:

• 1 ≤ T ≤ 200
• 0 ≤ N ≤ 5,000
• 0 ≤ r, g, b ≤ 255
• 1^st testcase = sample input
• 2^nd,3^rd testcases only contain operations “+ r g b” , "? r g b", "PrintSet"
• 4~6^th testcases contain operations “+ r g b”, “? r g b”, "- r g b", "PrintSet"

Output

For each test case, output one line with “Case #x:”, where x is the test case number (starting from 1).
Then print the result of each “? r g b”/“PrintSet” for one line.
Remember '\n' for the end of each line.

Sample Input  Download

Sample Output  Download

Partial Judge Code

12793.cpp

Partial Judge Header

12793.h

Tags

Add Tag

Discuss