P2650 Danmaku Assessment

zeromaker is clumsy, but he likes to play Touhou Project; EX and the like are his favorites.

zeromaker has conducted in-depth research on controlling his field of view for danmaku. Each danmaku appears in zeromaker’s field of view during a specific time interval, and is invisible outside that interval. In zeromaker’s opinion, the more danmaku are within the field of view, the harder the stage becomes, because this means @#￥%. Now, to evaluate the difficulty of a stage, he has already learned when each danmaku appears within his field of view. He wants to know, within a given time period, how many distinct danmaku have ever appeared in his field of view. Note: Here, “seconds” are treated as time instants. A danmaku is considered to have appeared in the field of view if and only if the observation interval and the danmaku’s appearance interval overlap with positive length; endpoint-only contact (for example, a danmaku ends at second $2$ and the observation starts at second $2$) does not count as appearing. # Description The first line contains two integers $n$, $m$, indicating there are $n$ danmaku in total, and zeromaker has $m$ queries. The next $n$ lines each contain two integers $a$, $b$, meaning this danmaku appears in zeromaker’s field of view starting at second $a$ and lasts for $b$ seconds. The following $m$ lines each contain two integers $x$, $y$, meaning starting from second $x$, over $y$ seconds, ask how many danmaku have appeared at any time in that interval. Note: Here, “seconds” are time instants. A danmaku is considered to have appeared in the field of view if and only if the observation interval and the danmaku’s appearance interval overlap with positive length; endpoint-only contact (e.g., the danmaku ends at second $2$ while the observation starts at second $2$) does not count as appearing.

The first line contains two integers $n$, $m$. The next $n$ lines each contain two integers $a$, $b$, where the danmaku appears at second $a$ and lasts for $b$ seconds. The next $m$ lines each contain two integers $x$, $y$, asking: from second $x$, over $y$ seconds, how many danmaku have ever appeared.

Output $m$ lines, where each line is the answer to one of zeromaker’s queries.

Sample 1 explanation: ```text 0 1 2 3 4 5 6 7 8 9 10 11 12 13 弹幕1 |--------------| 弹幕2 |-----------------------------| 弹幕3 |-----------------------| 视野1 |-----------------| 视野2 |-----| ``` Sample 2 explanation: ```text 0 1 2 3 4 5 6 7 8 9 10 11 弹幕1 |-----------------------------| 视野1 |--| 视野2 |--| ``` Constraints: - $30\%$ of the testdata: $n, m \le 10^3$. - $100\%$ of the testdata: $1 \le n, m \le 10^5$, $0 \le x, y, a, b \le 2^{31} - 1$. Translated by ChatGPT 5