Description

对于一个长度为 \(n\) 的序列 \(a_1, a_2, \ldots, a_n\), 其前缀和 (Prefix Sum)\(S_i\) 为前 \(i\) 个元素的和, 即 \(\sum_{k=1}^{i} a_i\). 而前缀和的前缀和 (Preprefix sum) 就是把前缀和序列 \(S_1, S_2, \ldots, S_n\) 作为原序列, 再求一次前缀和. 记再次求得的前缀和序列的第 \(i\) 位为 \(SS_i\).

现在给定一个长度为 \(n\) 的序列 \(a_1, a_2, \ldots, a_n\), 有两种操作:

  1. Modify i x 将 \(a_i\) 的值改为 \(x\);
  2. Query i 询问 \(SS_i\) 的值.

请编写一个程序来实现这两种操作.

Input

第一行给出两个整数 \(n, m\). 分别表示序列长度和操作个数;

接下来一行有 \(n\) 个数, 即给定的序列 \(a_1, a_2, \ldots, a_n\);

接下来 \(m\) 行, 每行对应一个操作, 格式见题目描述.

Output

对于每个询问操作, 输出一行, 表示所询问的 \(SS_i\) 的值.

Sample Input

5 3
1 2 3 4 5
Query 5
Modify 3 2
Query 5

Sample Output

35
32

Data Range

对于所有数据, 满足 \(1 \leq n, m \leq 10^5\), 且在任意时刻 \(0 \leq a_i \leq 10^5\).

Explanation

我们考虑这样一个递推公式:

\[\begin{aligned} SS_n &= \sum_{i=1}^{n} S_i\\ &= \sum_{i=1}^{n} \sum_{j=1}^{i} a_i\\ &= \sum_{i=1}^{n} (n + 1 - i) \cdot a_i\\ &= n \cdot \sum_{i=1}^{n} a_i - \sum_{i=1}^{n} (i - 1) \cdot a_i \end{aligned}\]

然后发现左边和右边两个都是可以分别用树状数组或线段树维护的, 但是树状数组代码行数 更少, 所以我就写了树状数组.

所以说这是一道结论题, 随便推一下就可以得到结果了.

Source Code

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>

using namespace std;
typedef long long lli;
const int maxn = 100100;

class BinaryIndexedTree
{
public:
    lli dat[maxn];
    int n;
    lli query(int x)
    {
        lli sum = 0;
        for (; x > 0; x -= x & -x)
            sum += dat[x];
        return sum;
    }
    void change(int x, lli v)
    {
        for (; x <= n; x += x & -x)
            dat[x] += v;
        return ;
    }
    void init(int n)
    {
        this->n = n;
        memset(dat, 0, sizeof(dat));
        return ;
    }
} bit1, bit2;

int n, m;
lli arr[maxn];
char str[64];

int main(int argc, char** argv)
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%lld", &arr[i]);
    // Initializing BIT tree.
    bit1.init(n);
    bit2.init(n);
    for (int i = 1; i <= n; i++) {
        bit1.change(i, arr[i]);
        bit2.change(i, (i-1) * arr[i]);
    }
    // Can you answer these queries?
    for (int idx = 1; idx <= m; idx++) {
        lli b; lli c;
        scanf("%s", str);
        if (str[0] == 'Q') {
            scanf("%lld", &b);
            lli res = b * bit1.query(b) - bit2.query(b);
            printf("%lld\n", res);
        } else if (str[0] == 'M') {
            scanf("%lld%lld", &b, &c);
            lli tmp = c - arr[b];
            arr[b] += tmp;
            bit1.change(b, tmp);
            bit2.change(b, (b-1) * tmp);
        }
    }
    return 0;
}