Milk Sum

题目描述

注意：本题时间限制为 4s，是默认值的 2 倍。 农夫约翰有 $N$ 头奶牛（$1\le N\le 1.5\cdot 10^5$），它们的产奶量为整数 $a_1,\dots,a_N$。也就是说，第 $i$ 头奶牛每分钟产奶 $a_i$ 单位，其中 $0 \leq a_i \leq 10^8$。

每天早上，农夫约翰一开始让全部 $N$ 头奶牛都连接在谷仓里的挤奶机上。他必须将它们一头一头地解开并送出去进行日常锻炼。第一头送出去的奶牛只挤奶 1 分钟后就被解开；第二头送出去的奶牛在又过了 1 分钟后被解开；以此类推。因此，第一头送出去的奶牛（设为奶牛 $x$）只在挤奶机上待 1 分钟，她对总产奶量的贡献为 $a_x$。第二头送出去的奶牛（设为奶牛 $y$）总共在挤奶机上待 2 分钟，因此贡献 $2a_y$。第三头送出去的奶牛（设为奶牛 $z$）贡献 $3a_z$，依此类推。设 $T$ 表示农夫约翰以最优顺序解开奶牛时，能够收集到的最大总产奶量。

农夫约翰想知道，如果牛群中的某些产奶量不同，$T$ 会受到怎样的影响。对于每个查询（共 $Q$ 个，$1\le Q\le 1.5\cdot 10^5$），由两个整数 $i$ 和 $j$ 指定，请计算如果将 $a_i$ 设为 $j$（$0 \leq j \leq 10^8$），新的 $T$ 会是多少。注意，每个查询考虑的是一次临时的潜在更改，并且与其他查询相互独立；也就是说，在考虑下一个查询之前，$a_i$ 会恢复为原来的值。

输入格式

第一行包含 $N$。 第二行包含 $a_1\dots a_N$。 第三行包含 $Q$。 接下来 $Q$ 行每行包含两个用空格分隔的整数 $i$ 和 $j$。

输出格式

对于每个查询，单独一行输出对应的 $T$ 的值。

5
1 10 4 2 6
3
2 1
2 8
4 5

55
81
98

提示

对于第一个查询，$a$ 将变为 $[1,1,4,2,6]$，并且 $T = 1 \cdot 1 + 2 \cdot 1 + 3 \cdot 2 + 4 \cdot 4 + 5 \cdot 6 = 55$。 对于第二个查询，$a$ 将变为 $[1,8,4,2,6]$，并且 $T = 1 \cdot 1 + 2 \cdot 2 + 3 \cdot 4 + 4 \cdot 6 + 5 \cdot 8 = 81$。 对于第三个查询，$a$ 将变为 $[1,10,4,5,6]$，并且 $T = 1 \cdot 1 + 2 \cdot 4 + 3 \cdot 5 + 4 \cdot 6 + 5 \cdot 10 = 98$。 SCORING: Inputs 2-4: $N,Q\le 1000$ Inputs 5-11: 没有额外限制。 题目贡献者：Benjamin Qi

标签: USACO|2023|Silver

来源

USACO|2023|Silver