Description

A segment tree is a special binary tree that satisfies the following properties:
Each node corresponds to an interval and has an integer weight.
The interval corresponding to the root is $[1,n]$.
If a node corresponds to interval $[l,r]$ and $l<r$, then its left child and right child correspond to intervals $[l,m]$ and $[m+1,r]$, where $m=\lfloor\frac{l+r}{2}\rfloor$.
If a node corresponds to interval $[l,r]$ and $l=r$, then this node is a leaf.
If a node is not a leaf, then its weight equals the sum of the weights of its left child and right child.

Chtholly (ke duo li, 珂朵莉) needs to maintain a segment tree. The initial weights of the leaves are $0$. Then $m$ operations will be performed:

Operation $1$: given $l,r,a$, for every $x$ ($l\leq x\leq r$), add $a$ to the weight of the leaf corresponding to $[x,x]$, and the weights of non-leaf nodes change accordingly.

Operation $2$: given $l,r,a$, ask how many nodes in the segment tree satisfy that the interval corresponding to this node is contained in $[l,r]$, and its weight is less than or equal to $a$.

Input Format

The first line contains two integers $n,m$.

In the next $m$ lines, each line contains four integers $op,l,r,a$, representing one operation, where $op$ indicates the operation type.

Output Format

For each operation with $op=2$, output one line containing one integer, which is the answer.

3 3
1 2 3 9
2 1 2 1
2 1 3 1

1
1

Hint

Idea: zcysky.

Solution: nzhtl1477 ( $O( m\sqrt{n\log n})$ solution ), ccz181078 ( $O( m\sqrt{n})$ solution ).

Code: nzhtl1477 ( $O( m\sqrt{n} \log n)$ code ), ccz181078 ( $O( m\sqrt{n\log n})$ code ).

Data: nzhtl1477.

Constraints: for $100\%$ of the testdata, $1\leq n,m\leq 10^5$, $1\leq l\leq r\leq n$, $1\leq op\leq 2$, $-10^5\leq a\leq 10^5$.

Translated by ChatGPT 5