A5680. 「THUPC 2024」古明地枣的袜子
编程题
NOI/NOI+/CTSC
知识点
题目描述
你需要维护一个序列 $a_1,\dots,a_n$ 。
给定一个操作序列 $(x_1,y_1),\dots,(x_n,y_n)$ ，操作 $(x,y)$ 表示将 $a_1,\dots,a_x$ 的值加上 $y$ 。
共 $m$ 次查询，每次查询给出 $l,r$ ，问对初始值为 $0$ 的序列 $a$ 依次执行操作 $(x_l,y_l),\dots,(x_r,y_r)$ ，最后 $\mathop\max\limits_{i=1}^n a_i$ 的值。
给定一个操作序列 $(x_1,y_1),\dots,(x_n,y_n)$ ，操作 $(x,y)$ 表示将 $a_1,\dots,a_x$ 的值加上 $y$ 。
共 $m$ 次查询，每次查询给出 $l,r$ ，问对初始值为 $0$ 的序列 $a$ 依次执行操作 $(x_l,y_l),\dots,(x_r,y_r)$ ，最后 $\mathop\max\limits_{i=1}^n a_i$ 的值。
输入格式
第一行两个整数 $n,m$ （$1\le n,m\le 5\times 10^5$）；
接下来 $n$ 行每行两个整数 $x_i,y_i$（$1\le x_i\le n, |y_i|\le n$）；
接下来 $m$ 行，每行两个整数 $l,r$（$1\le l\le r\le n$）。
接下来 $n$ 行每行两个整数 $x_i,y_i$（$1\le x_i\le n, |y_i|\le n$）；
接下来 $m$ 行，每行两个整数 $l,r$（$1\le l\le r\le n$）。
输出格式
输出 $m$ 行，每行一个整数，表示每次查询的答案。
输入输出样例
输入 #1
6 5 6 4 2 6 5 -5 3 6 1 2 3 6 1 6 1 6 2 6 2 6 5 6
输出 #1
19 19 15 15 8