[USACO23OPEN] Milk Sum S
重生之我再也不敢乱用 lower_bound 了.
显然看到这种套路题目首先复制一个数组, 然后排序前缀和初始化答案. 查找数字的位置直接在排序完后的数组上二分即可.
#include<iostream>
#include<algorithm>
#define P(A) A=-~A
typedef long long LL;
#define NUMBER1 150000
#define NUMBER2 100000000
LL pre_ans(0);
int n,a[NUMBER1+5],b[NUMBER1+5];
LL sum[NUMBER1+5];
signed main(){std::cin.tie(nullptr)->std::ios::sync_with_stdio(false);std::cout.tie(nullptr);std::cin>>n;for(int i=1;i<=n;P(i)){std::cin>>a[i];b[i]=a[i];}std::sort(b+1,b+1+n);for(int i=1;i<=n;P(i)){pre_ans+=1ll*i*b[i];sum[i]=sum[i-1]+b[i];}
}
我们设 \(p_1\) 为 \(a[i]\) 在排序后数组的位置, \(p_2\) 为 \(j\) 在排序后数组的位置. 显然必有:
p1=std::lower_bound(b+1,b+1+n,a[i])-b;
p2=std::lower_bound(b+1,b+1+n,j)-b;
然后我们开始分情况讨论, 当 \(p_1=p_2\) 时, 直接替换即可
if(p1==p2)std::cout<<pre_ans+1ll*p1*(j-a[i])<<'\n';
当 \(p1>p2\) 时, 显然对于初始化的 \(ans\) 而言, 从 \([p_2,p_1-1]\) 的数都要往右移动一位, 然后正常替换即可, 那么则有:
if(p1>p2)std::cout<<pre_ans-1ll*p1*a[i]+sum[p1-1]-sum[p2-1]+1ll*p2*j<<'\n';
同样, 当 \(p1<p2\) 时, 显然对于初始化的 \(ans\) 而言, 从 \([p_1+1,p_2]\) 的数都要往右移动一位, 然后正常替换即可, 那么则有:
std::cout<<pre_ans-1ll*p1*a[i]+1ll*p2*j+sum[p1]-sum[p2]<<'\n';
然后根据样例而言:
5
1 10 4 2 6
3
2 1
2 8
4 5
你会发现应该输出:
55
81
98
结果输出:
55
81
97
实际上是 lower_bound 出问题了. 因为 lower_bound 当没找到相等的数时, 会自然而然跳到下一位.
下面我们将详细讲述 \(p_2\) 跳到下一位的影响.
当 \(p_1=p_2\) 时, 当 \(j=b_{p_1}\) 显然成立, 不用讨论. 但若 \(j=\ne b_{p_2}\) 时, 则有 \(b_{p_2}>j\geq b_{p_2-1}\), 我们将 \(b_{p_2}\) 替换为 \(j\) 显然满足单调性. 此时 \(p_2\) 的越位是 有必要的.
当 \(p_1>p_2\) 时, 我们的要求是把 \(b_{p_1}\) 删了, 显然答案减去 \(p_1b_{p_1}\), 由于 \(b\) 是不严格单调递增的 , 所以必有 \(b_{p_2}\geq j\), 所以我们要把 \([p_2,p_1-1]\) 向右移动一位, 然后把 \(j\) 放进去, 此时答案加上 \(p_2j+sum_{p_1-1}-sum_{p_2-1}\).
当 \(p_1<p_2\) 时, 我们的要求是把 \(b_{p_1}\) 删了, 显然答案减去 \(p_1b_{p_1}\), 由于 \(b\) 是不严格单调递增的 , 所以必有 \(b_{p_2}\geq j\). 我们把 \(p_1\) 删了后, 如果 \(b_{p_2}>j\) 时, 为了维持不严格单调递增, 我们只能往 \(p_2\) 的左边加 \(j\). 即如果我们发现 \(b_{p_2}\ne j\) 时, 自动把 \(p_2\) 向左移一位, 然后加上 \(p_2j\), 减去 \(sum_{p_2}-sum_{p_1}\).
所以代码应该这么写:
else{if(b[p2]!=j)--p2;std::cout<<pre_ans-1ll*p1*a[i]+1ll*p2*j+sum[p1]-sum[p2]<<'\n';
}
代码:
#include<iostream>
#include<algorithm>
#define P(A) A=-~A
typedef long long LL;
#define NUMBER1 150000
#define NUMBER2 100000000
LL pre_ans(0);
int n,a[NUMBER1+5],b[NUMBER1+5];
LL sum[NUMBER1+5];
signed main(){std::cin.tie(nullptr)->std::ios::sync_with_stdio(false);std::cout.tie(nullptr);std::cin>>n;for(int i=1;i<=n;P(i)){std::cin>>a[i];b[i]=a[i];}std::sort(b+1,b+1+n);for(int i=1;i<=n;P(i)){pre_ans+=1ll*i*b[i];sum[i]=sum[i-1]+b[i];}int q;std::cin>>q;for(int i,j,p1,p2;q--;){std::cin>>i>>j;p1=std::lower_bound(b+1,b+1+n,a[i])-b;p2=std::lower_bound(b+1,b+1+n,j)-b;if(p1==p2)std::cout<<pre_ans+1ll*p1*(j-a[i])<<'\n';else if(p1>p2)std::cout<<pre_ans-1ll*p1*a[i]+sum[p1-1]-sum[p2-1]+1ll*p2*j<<'\n';else{if(b[p2]^j)--p2;std::cout<<pre_ans-1ll*p1*a[i]+1ll*p2*j+sum[p1]-sum[p2]<<'\n';}}return 0;
}