Sereja and Tree

题意翻译

题意： 定义一种新型二叉树,定义在下面. 你有一个n层的新型二叉树,每个点初始有一个空数集,有m组操作,操作有两种: 1.形如<1,t,l,r,x>,在点(t,[l,r])的数集中添加数x. 2.形如<2,t,v>,询问以点(t,v)为根的子树中所有点的数集的并的元素个数. 新型二叉树定义： 树的定义:https://en.wikipedia.org/wiki/Tree_(graph_theory) 一个数对(t,id)表示一个点,代表这个点是第t层的第id个点,根为(1,1). 对于每个点,当id为2的幂次时,这个点有两个孩子,否则只有一个孩子. 以下是一个4层新型二叉树.  4层新型二叉树 新型二叉树的生成伪代码: ``` //the global data are integer arrays cnt[], left[][], right[][] cnt[1] = 1; fill arrays left[][], right[][] with values -1; for(level = 1; level < n; level = level + 1){ cnt[level + 1] = 0; for(position = 1; position <= cnt[level]; position = position + 1){ if(the value of position is a power of two){ // that is, 1, 2, 4, 8... left[level][position] = cnt[level + 1] + 1; right[level][position] = cnt[level + 1] + 2; cnt[level + 1] = cnt[level + 1] + 2; }else{ right[level][position] = cnt[level + 1] + 1; cnt[level + 1] = cnt[level + 1] + 1; } } } After the pseudo code is run, cell cnt[level] contains the number of vertices on level level. Cell left[level][position] contains the number of the vertex on the level level + 1, which is the left child of the vertex with index (level, position), or it contains -1, if the vertex doesn't have a left child. Similarly, cell right[level][position] is responsible for the right child. You can see how the tree with n = 4 looks like in the notes. ``` 输入数据： 第一行n,m. 接下来m行,每行一组操作,形如<1,t,l,r,x> or <2,t,v>. 输出数据： 按顺序输出操作2中的答案. 注意： 数集类似于set,自动去重. 数据范围： n,m:[1,7000] t:[1,n] x[1,1e6] 感谢@尘染梦 提供的翻译

题目描述

Sereja adores trees. Today he came up with a revolutionary new type of binary root trees. His new tree consists of $ n $ levels, each vertex is indexed by two integers: the number of the level and the number of the vertex on the current level. The tree root is at level $ 1 $ , its index is $ (1,1) $ . Here is a pseudo code of tree construction. `<br></br>//the global data are integer arrays cnt[], left[][], right[][]<br></br><br></br>cnt[1] = 1;<br></br>fill arrays left[][], right[][] with values -1;<br></br>for(level = 1; level < n; level = level + 1){<br></br> cnt[level + 1] = 0;<br></br> for(position = 1; position <= cnt[level]; position = position + 1){<br></br> if(the value of position is a power of two){ // that is, 1, 2, 4, 8...<br></br> left[level][position] = cnt[level + 1] + 1;<br></br> right[level][position] = cnt[level + 1] + 2;<br></br> cnt[level + 1] = cnt[level + 1] + 2; <br></br> }else{<br></br> right[level][position] = cnt[level + 1] + 1;<br></br> cnt[level + 1] = cnt[level + 1] + 1;<br></br> }<br></br> }<br></br>}<br></br>`After the pseudo code is run, cell cnt\[level\] contains the number of vertices on level $ level $ . Cell left\[level\]\[position\] contains the number of the vertex on the level $ level+1 $ , which is the left child of the vertex with index $ (level,position) $ , or it contains -1, if the vertex doesn't have a left child. Similarly, cell right\[level\]\[position\] is responsible for the right child. You can see how the tree with $ n=4 $ looks like in the notes. Serja loves to make things complicated, so he first made a tree and then added an empty set $ A(level,position) $ for each vertex. Then Sereja executes $ m $ operations. Each operation is of one of the two following types: - The format of the operation is " $ 1 $ $ t $ $ l $ $ r $ $ x $ ". For all vertices $ level,position $ $ (level=t; l<=position<=r) $ add value $ x $ to set $ A(level,position) $ . - The format of the operation is " $ 2 $ $ t $ $ v $ ". For vertex $ level,position $ $ (level=t,position=v) $ , find the union of all sets of vertices that are in the subtree of vertex $ (level,position) $ . Print the size of the union of these sets. Help Sereja execute the operations. In this problem a set contains only distinct values like std::set in C++.

输入输出格式

输入格式

The first line contains integers $ n $ and $ m $ $ (1<=n,m<=7000) $ . Next $ m $ lines contain the descriptions of the operations. The operation of the first type is given by five integers: $ 1 $ $ t $ $ l $ $ r $ $ x $ $ (1<=t<=n; 1<=l<=r<=cnt[t]; 1<=x<=10^{6}) $ . The operation of the second type is given by three integers: $ 2 $ $ t $ $ v $ $ (1<=t<=n; 1<=v<=cnt[t]) $ .

输出格式

For each operation of the second type, print the answer on a single line.

输入输出样例

输入样例 #1

4 5
1 4 4 7 1
1 3 1 2 2
2 1 1
2 4 1
2 3 3

输出样例 #1

2
0
1

说明

You can find the definitions that are used while working with root trees by this link: http://en.wikipedia.org/wiki/Tree\_(graph\_theory) You can see an example of a constructed tree at $ n=4 $ below.