UOJ Logo

NOI.AC

1S 512MB

#51. array

Statistics

题目描述

你的面前有一个长度为 $n$ 的数组。初始时,第 $i$ 个位置的元素为 $i$(即所有位置上的元素依次为从 1 到 $n$ 的正整数)。

接下来,你需要帮我依次完成 $m$ 个操作。每个操作可能是:

  • A $p$ $q$,表示你需要修改数组中的所有元素。具体地,第 $i$ 个位置的元素被修改成 $p \times i + q$。
  • B $x$ $y$,表示你需要修改数组中的单个元素。具体地,第 $x$ 个位置的元素被修改成 $y$。

其中上述 $p,q,x,y$ 均为整数。

每次操作结束后,你需要输出数组中所有元素的和。

输入格式

从标准输入读入数据。

输入的第一行包含两个数 $n, m$。

接下来 $m$ 行,每行依次表示一个操作,格式为A $p$ $q$或者B $x$ $y$,意义如上所述。

同一行输入的相邻两个元素之间,用一个空格隔开。

输出格式

输出到标准输出。

输出共 $m$ 行,每行表示每个操作结束之后,数组中所有数的和。

样例

输入

5 4
B 1 5
A -1 0
A 1 2
A 2 -5

输出

19
-15
25
5

解释

  • 第1次操作结束后,数组变为{5, 2, 3, 4, 5};
  • 第2次操作结束后,数组变为{-1, -2, -3, -4, -5};
  • 第3次操作结束后,数组变为{3, 4, 5, 6, 7};
  • 第4次操作结束后,数组变为{-3, -1, 1, 3, 5}。

    样例

输入

50000000 4
A 1 0
A 1000 0
A 1000 1000000000
B 50000000 -1000000000

输出

1250000025000000
1250000025000000000
1300000025000000000
1299999973000000000

各测试点数据规模与约定

对于测试点 1,2,保证 $n \leq 100$。

对于测试点 3,4,保证所有的操作均为 B 类型。

对于测试点 5,6,7,8,保证所有的操作均为 A 类型。

对于所有数据,保证 $n \leq 50,000,000, m \leq 500,000$。对于每个操作,保证 $|p| \leq 1000, |q|,|y| \leq 10^9, 1 \leq x \leq n$。