Chef and Red Black Tree
All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
Chef likes trees a lot. Today he has an infinte full binary tree (each node has exactly two childs) with special properties.
Chef's tree has the following special properties :
- Each node of the tree is either colored red or black.
- Root of the tree is black intially.
- Both childs of a red colored node are black and both childs of a black colored node are red.
The root of the tree is labelled as 1. For a node labelled v, it's left child is labelled as 2*v and it's right child is labelled as 2*v+1.
Chef wants to fulfill Q queries on this tree. Each query belongs to any of the following three types:
- Qi Change color of all red colored nodes to black and all black colored nodes to red.
- Qb x y Count the number of black colored nodes on the path from node x to node y (both inclusive).
- Qr x y Count the number of red colored nodes on the path from node x to node y (both inclusive).
Help chef accomplishing this task.
First line of the input contains an integer Q denoting the number of queries. Next Q lines of the input contain Q queries (one per line). Each query belongs to one of the three types mentioned above.
For each query of type Qb or Qr, print the required answer.
Qb 4 5
Qr 4 5
Qb 4 5
Qr 4 5
With the initial configuration of the tree, Path from node 4 to node 5 is 4->2->5 and color of nodes on the path is B->R->B.
- Number of black nodes are 2.
- Number of red nodes are 1.
After Query Qi, New configuration of the path from node 4 to node 5 is R->B->R.
- Number of black nodes are 1.
- Number of red nodes are 2.
- Subtask #1: 1<=Q<=100 1<=x,y<=1000 : 27 pts
- Subtask #2: 1<=Q<=103 1<=x,y<=105 : 25 pts
- Subtask #3: 1<=Q<=105 1<=x,y<=109 : 48 pts
|Tags||ad-hoc, easy, graph, lca, ma5termind, nov14|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.