All submissions for this problem are available.
Read problems statements in Mandarin Chinese , Russian and Vietnamese as well.
Chef has recently learnt about binary trees and immediately fell in love with them. His best friend Shasha has promised him to gift a binary tree only if he is able to show his love for binary trees by solving the following problem about binary trees.
Given a complete binary tree T consisting of N nodes labelled from 1 to N. The node with label 1 is the root of the tree. For a node labelled v, its' left child will be labelled as 2*v (provided it exists) and right child as 2*v+1 (provided it exists).
Initially, all the nodes of tree are uncolored.
Chef has to perform Q queries on tree T where each query can have one of the following three types:
- 1 X K
Update the tree T such that node X becomes uncolored, all the nodes at distance 1 from X get colored with color 1, all nodes at distance 2 from X get colored with color 2, and so on up to nodes at distance K from X.
Formally, color all nodes that are at distance (1 ≤ D ≤ K) units from node X with color D and make node X colourless.
Please note that when we say node at distance D from node X, you have to consider all the nodes in the tree, not just the ones in the subtree of X.
- 2 X Y
Count the number of distinct colors on the unique simple path from node X to node Y.
- 3 X
Count the number of distinct colors in the subtree rooted at node X.
The first line of input contains two space separated integer numbers N and Q denoting the number of nodes in the tree T and number of queries to be processed respectively.
Each of the following Q lines contains a query of one of the above mentioned three types.
For each query of type 2 and 3, print the sought answer.
- 1 ≤ N ≤ 105
- 1 ≤ Q ≤ 50000
- 1 ≤ X, Y ≤ N
- 0 ≤ K ≤ 105
- Subtask 1 (32 pts) : 1 ≤ N, Q ≤ 1000
- Subtask 2 (68 pts) : original constraints
Input 10 10 2 3 5 3 1 1 2 2 2 3 5 1 3 2 2 3 5 3 1 1 7 5 3 1 2 3 5 output 0 0 2 2 2 5 4
|Tags||data-structure, ltime35, ma5termind, queries, segment, tree|
|Time Limit:||3 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, 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, SCM chicken, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.