#1383. [USACO23OPEN] Milk Sum S
[USACO23OPEN] Milk Sum S
题目描述
注意:本题的时间限制为 4 秒,是默认时间限制的 2 倍。
Farmer John 的 头奶牛的产奶量为整数 。也就是说,第 头奶牛每分钟产 单位的牛奶。
每天早上,Farmer John 会将所有 头奶牛连接到谷仓的挤奶机上。他需要依次断开连接,将奶牛送去进行日常锻炼。第一头奶牛在挤奶 1 分钟后被断开连接,第二头奶牛在再挤奶 1 分钟后被断开连接,依此类推。由于第一头奶牛(假设是奶牛 )只在挤奶机上停留了 1 分钟,她总共贡献了 单位的牛奶。第二头奶牛(假设是奶牛 )在挤奶机上停留了总共 2 分钟,因此贡献了 单位的牛奶。第三头奶牛(假设是奶牛 )贡献了 单位的牛奶,依此类推。设 表示 Farmer John 以最优顺序断开奶牛连接时,可以收集到的最大总牛奶量。
Farmer John 很好奇,如果某些奶牛的产奶量发生变化, 会如何变化。对于每个由两个整数 和 指定的 个查询,请计算如果将 设置为 ,新的 值会是多少。注意,每个查询都是独立的临时变化,即在考虑下一个查询之前, 会恢复为原始值。
输入格式
第一行包含 。
第二行包含 。
第三行包含 。
接下来的 行,每行包含两个用空格分隔的整数 和 。
输出格式
请为每个查询输出一行,表示对应的 值。
样例
5
1 10 4 2 6
3
2 1
2 8
4 5
55
81
98
题目来源:洛谷 P9186