Lazy Segment Tree Duplication and Query

A girl named Jiutiao Kelian loves data structures, and her favorite is the segment tree. In this problem, you are given a segment tree built on the interval \([1,n]\) with all lazy tags initially set to 0. The tree is built in the usual way: each node covers an interval and, if its interval has more than one element, it has two children covering the left and right halves respectively.

The segment tree supports one update operation Modify(Node, L, R, l, r) using lazy propagation. The pseudo‐code for Modify is given below (note that the lazy array is called \(tag\)). In the pseudo‐code, \(Lson(Node)\) and \(Rson(Node)\) denote the left and right children of Node respectively. The operation works as follows:

\[ \begin{aligned} &\textbf{function } Modify(Node, L, R, l, r): \\ &\quad \textbf{if } (l \le L \textbf{ and } R \le r) \textbf{ then} \{ \\ &\qquad \; tag[Node] = 1; \\ &\qquad \; return; \\ &\quad \} \\ &\quad \text{if } (tag[Node] == 1) \text{ then return;} \\ &\quad mid = \lfloor (L+R)/2 \rfloor; \\ &\quad \textbf{if } (l \le mid) Modify(Lson(Node), L, mid, l, r); \\ &\quad \textbf{if } (r > mid) Modify(Rson(Node), mid+1, R, l, r); \end{aligned} \]

Note that when a node is updated with a full-cover (i.e. its interval is completely contained in \([l, r]\)), its lazy tag is set to 1 and no further recursion is done. Otherwise (for partial overlap) the update attempts to recursively update its children (provided the node is not already lazily marked).

Initially, you have one segment tree (numbered 1) built on \([1,n]\) with all tag values equal to 0. Then, you will perform \(m\) operations. There are two kinds of operations:

• 1 l r: Suppose you currently have \(t\) segment trees. For each tree, you make two copies (the entire tree along with its tag values). The original tree with index \(i\) produces two copies with new indices \(2i-1\) and \(2i\) (so after copying, you have \(2t\) trees). Then, for every segment tree whose index is odd (i.e. 1-indexed odd), you perform Modify(root, 1, n, l, r) on that tree.
• 2: For each segment tree, define its weight as the number of nodes in the tree whose tag is 1. Output the sum of the weights of all trees.

Your task is to process the \(m\) operations. For each operation of type 2, output the current total weight.

inputFormat

The first line contains two integers \(n\) and \(m\) (\(1 \le n \le 10^5\), \(1 \le m \le 20\)) indicating the length of the segment tree range and the number of operations respectively.

Each of the next \(m\) lines contains an operation. An operation is either in the form:

• 1 l r (\(1 \le l \le r \le n\)) indicating that you should duplicate all trees and then perform Modify(root,1,n,l,r) on each tree with an odd index, or
• 2 indicating that you should output the total weight of all trees.

outputFormat

For each operation of type 2, output an integer on a new line -- the sum of the weights of all segment trees at that time.

sample

1 3
1 1 1
2
2

1
1

</p>