P6609 [Code+#7] Textbook-like Defile

This problem is exactly the same as [P5068 [Ynoi2015] I Am Back](https://www.luogu.com.cn/problem/P5068), but for consistency of the contest problems, the statement is shown and submissions are not accepted.

qwqwq. How much damage does Blue Dragon’s Defile deal? ------- When qwq plays Hearthstone, he can never play a textbook-like Defile, so he rewrote a new “Hearthstone” and changed the description of Defile to: “Randomly choose an integer as the damage value $d$ uniformly from $[L,R]$, deal $d$ damage to all minions. If any minion dies, cast this spell again, but the damage value is not re-randomized; if no minion dies, stop casting.” He also removed the limit on the number of minions on the board and the limit that Defile can trigger at most $14$ times. qwq wants to test how this modified Defile works, so he will perform a total of $m$ operations of the following types: 1. Add a minion with health $h$ to the board. Here, the health of any minion will not exceed $n$. 2. Given $[L,R]$, ask for the expected number of times Defile triggers. qwq can only do operation $1$, so he leaves operation $2$ to you.

The first line contains two integers $n\ m$ separated by spaces. The next $m$ lines each describe one operation: operation $1$ is written as $1\ h$, and operation $2$ is written as $2\ L\ R$.

To avoid outputting decimals, for each operation $2$, output one integer equal to the expected value multiplied by $(R-L+1)$.

For $19\%$ of the testdata, $n,m\le 10^3$. For another $19\%$ of the testdata, in every operation $2$, $L = R$. For another $19\%$ of the testdata, all operations $2$ occur after operations $1$. For another $19\%$ of the testdata, $m\le10^5$. For $100\%$ of the testdata, it is guaranteed that $1\le n\le 10^5$. In each operation $1$, $1\le h\le n$. In each operation $2$, $1\le L\le R\le n$, and $1\le m\le 10^6$. All values above are integers. Translated by ChatGPT 5