数字替换 Description 给你一个数列a，共N个数字，其值为a1到an 你可以将这个数列a打乱得到数列b 定义T=1 * b[1]+2 * b[2]+3 * b[3]+.....n * b[n],现希望T越大越好 然后发现问题太简单了 于是有以下Q个独立的操作,即你每次操作完成后，a数列又恢复成原样 每次操作给出x,y代表将ax替换成y 现在问你每次替换后，T的值为多少 Format Input 第一行给出N 第二行给出N个数字 接下给出Q 接下来Q行c++代码

我可以理解为，给定一个长度为 $N$ 的数列 $a$，定义 $T=\sum\limits_{i=1}^{N} i\times b_i$，其中 $b$ 是 $a$ 的一个排列。现在有 $Q$ 次操作，每次将 $a_x$ 替换成 $y$，求每次操作后 $T$ 的值。

输入格式：

第一行包含整数 $N$。

第二行包含 $N$ 个整数 $a_1,a_2,\dots,a_N$。

第三行包含整数 $Q$。

接下来 $Q$ 行，每行包含两个整数 $x,y$，表示将 $a_x$ 替换成 $y$。

输出格式：

输出共 $Q$ 行，每行输出一个整数，表示每次操作后 $T$ 的值。

输入样例：

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

输出样例：

29
33
29

算法1

暴力枚举，每次操作都重新计算 $T$ 的值，时间复杂度为 $O(NQ)$，会超时。

时间复杂度

参考文献

Python3 代码

算法2

优化的暴力枚举，每次操作只需计算发生了改变的元素，时间复杂度为 $O(QN)$，可以通过本题。

时间复杂度

参考文献

C++ 代码

算法3

使用树状数组优化，每次操作只需更新发生了改变的元素，时间复杂度为 $O(Q\log N)$。

时间复杂度

参考文献

C++ 代码

相关问题

栈的判断 description 给定n个数字,已知这些数字的入栈顺序为1,2, ,n,给定一个

栈是一种特殊的数据结构，它遵循“先进后出”的原则，即最后入栈的元素会最先出栈。根据问题描述，我们已知n个数字的入栈顺序为1，2，...，n，而我们需要判断给定的一个序列是否是栈的弹出顺序。

为了判断给定的序列是否是栈的弹出顺序，我们可以借助一个辅助栈来模拟栈的入栈和出栈过程。

具体操作如下：
1. 定义一个辅助栈和一个指针i，初始时i=0；
2. 遍历给定的序列，对于每一个元素，执行以下操作：
a. 若栈为空或当前栈顶元素不等于当前遍历到的序列元素，则将序列元素依次入栈；
b. 若当前栈顶元素等于当前遍历到的序列元素，则将当前栈顶元素出栈；
c. 每完成一次入栈或出栈操作，指针i向后移动一位；
3. 判断辅助栈是否为空，若为空则说明给定的序列是栈的弹出顺序，否则不是。

以上操作思路基于以下原理：在栈的弹出序列中，一个元素出栈之前，它之前的所有元素都必须先入栈。所以我们可以利用这个原理来判断给定的序列是否是栈的弹出顺序。

需要注意的是，以上操作仅适用于假设的入栈顺序为1，2，...，n的情况，对于其他入栈顺序的判断可能需要进行调整。

description编写一个函数,求一个3位数的各位数字之和。函数原型为int sum(int m);

下面是求一个3位数的各位数字之和的函数实现：

int sum(int m) {
    int sum = 0;
    
    // 提取个位数字
    int unit = m % 10;
    sum += unit;
    
    // 提取十位数字
    int ten = (m / 10) % 10;
    sum += ten;
    
    // 提取百位数字
    int hundred = m / 100;
    sum += hundred;
    
    return sum;
}

这个函数中使用了数学运算来提取数字的各个位数，然后将它们相加，最后返回结果。例如，对于输入的三位数123，这个函数会返回1+2+3=6。