P5063 [Ynoi Easy Round 2014] In the Forest Above the Sky

 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? 

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

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.

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

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