Background

If, I mean if,
I were going to die in five more days,
could you treat me a bit more gently?

Such good luck.
Sacrificing only me will be enough.
That is how it is.

Are you willing to grant my last wish now?
Um... well... for example... right.

Like letting you kiss me.
Would you?

Before I disappear,
I hold the wish that I do not want to disappear.
I hope someone will remember me.
I hope to leave behind a bond.
I wish for this—what is wrong with that?

Problem 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