Milk Sum (USACO Silver 2023 Open)
a[i] <= 1e8，有 N 头牛（1.5e5），Q 个查询（1.5e5）
显然牛按照 a[i] 升序被释放这样的方式，我们可以得到最大的产奶量。我们需要一种快速（ 或 ）的方法来计算每次查询后总产奶量的变化。因为计算过程是一个累加的过程，以及每次查询对累加进行一个局部的改变，所以考虑用前缀和这样的方法，只要细心一些，就不会错。
首先我们将 a[] 排序得到 b[]，并用 idx[i] 记录 a[i] 在 b[] 中的位置。
对于每个查询，如果 j < a[i]，那么第 i 头牛可能会被提前释放。我们用二分查找找到它的新位置 k，此时 k <= idx[i]。对于区间 [k, idx[i]) 内的每头牛，其产奶量会增加 b[l]。我们用前缀和计算变化量：psum[idx[i]-1] - psum[k-1]。
公式为：
ans = ans0 + psum[idx[i]-1] - psum[k-1] + k*j - idx[i]*a[i]
如果 j > a[i]，可以证明公式类似，但需要注意右侧的牛会向左移动一位。因此：
公式为：
ans = ans0 + psum[idx[i]] - psum[k] + k*j - idx[i]*a[i]
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
int a[150005], idx[150005];
pi b[150005];
ll psum[150005];
ll ans0;
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
b[i] = {a[i], i};
}
sort(b+1, b+n+1);
for (int i = 1; i <= n; i++) idx[b[i].s] = i;
for (int i = 1; i <= n; i++) psum[i] = psum[i-1] + b[i].f;
for (int i = 1; i <= n; i++) ans0 += (ll)b[i].f * i;
int q;
scanf("%d", &q);
while (q--) {
int i, j;
scanf("%d %d", &i, &j);
int k;
ll ans;
if (j < a[i]) {
k = lower_bound(b+1, b+n+1, make_pair(j, 0)) - b; // moving to the left
ans = ans0 + psum[idx[i]-1] - psum[k-1] + (ll)k*j - (ll)idx[i]*a[i];
} else {
k = lower_bound(b+idx[i]+1, b+n+1, make_pair(j, 0)) - b - 1; // moving to the right
ans = ans0 + psum[idx[i]] - psum[k] + (ll)k*j - (ll)idx[i]*a[i];
}
printf("%lld\n", ans);
}
return 0;
}