C.序列(array)

题目描述

你需要维护两个初值为 $0$ 的序列 $a_1,\dots,a_n$ 和 $b_1,\dots,b_n$ ；

共 $m$ 次操作，每次操作给出 $x,y$ ，将 $a_x$ 修改为 $y$ ，然后对 $i=1,\dots,n$ 将 $b_i$ 加上 $\max \limits_{j=1}^i a_j$ ，然后查询 $\sum\limits_{i=1}^x b_i$ 。

输入格式

第一行两个整数 $n,m$；

接下来 $m$ 行，每行两个整数 $x,y$ 表示一次操作。

输出格式

共 $m$ 行，每行一个整数表示答案。

输入样例 #1

5 6
3 4
1 2
2 4
1 4
3 5
1 2

输出样例 #1

4
2
10
8
47
14

「样例 #2」

见题目附件下的 ex_array/array0_02.in 与 ex_array/array0_02.out。

该样例满足 $25\%$ 的条件限制。

「样例 #3」

见题目附件下的 ex_array/array0_03.in 与 ex_array/array0_03.out。

该样例满足 $50\%$ 的条件限制。

「样例 #4」

见题目附件下的 ex_array/array0_04.in 与 ex_array/array0_04.out。

该样例满足 $75\%$ 的条件限制。

「样例 #5」

见题目附件下的 ex_array/array0_05.in 与 ex_array/array0_05.out。

该样例满足 $100\%$ 的条件限制。

附件

file

数据范围

对于 $25\%$ 的数据，满足 $n,m\le 10^2$。

对于 $50\%$ 的数据，满足 $n,m\le 5\times 10^3$.

对于另外 $25\%$ 的数据，每次操作保证 $a_x\le y$。

对于 $100\%$ 的数据，满足 $1\le n,m\le 10^6$，$1\le x,y\le n$。