数字替换 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++ 代码