P10540 [THUPC 2024 Finals] Koishi Date's Socks

You need to maintain a sequence $a_1,\dots,a_n$. You are given an operation sequence $(x_1,y_1),\dots,(x_n,y_n)$. An operation $(x,y)$ means adding $y$ to the values of $a_1,\dots,a_x$. There are $m$ queries. Each query gives $l,r$ and asks: starting from an initial sequence $a$ where all values are $0$, execute the operations $(x_l,y_l),\dots,(x_r,y_r)$ in order. What is the final value of $\max\limits_{i=1}^n a_i$?

The first line contains two integers $n,m$ ($1\le n,m\le 5\times 10^5$). The next $n$ lines each contain two integers $x_i,y_i$ ($1\le x_i\le n, |y_i|\le n$). The next $m$ lines each contain two integers $l,r$ ($1\le l\le r\le n$).

Output $m$ lines, each containing one integer, which is the answer to each query.

**Source and Acknowledgements** From the THUPC2024 (2024 Tsinghua University Student Programming Contest and Intercollegiate Invitational) finals. For testdata, statement, reference solution, editorial, etc., please refer to the official THUPC repository . Translated by ChatGPT 5