首先将 \(a_i\) 变成 \(a_i-b_i\)
发现如果不管 \(a_1\) 的话，需要什么操作是可以预处理出来的
然后单独把 \(a_1\) 弄成0，需要什么操作也是可以预处理出来的
要求最小化操作次数，发现这两部分中有一些在同一位置的恰好相反的操作是可以消掉的
注意一个事情，若 \(a_1\) 恰好增加（或减少）1的话，其它任意位置需要的额外操作数不超过1
实际上位置 \(i\) 需要的操作是给这个位置加上一个 \(\mu(i)\)，可以根据实际意义容斥证明
于是令 \(A\) 为当 \(a_i\) 增加1时需要进行加1操作的集合，\(B\) 为需要减1操作的集合
维护 \(val1\) 为 \(A\) 中不考虑 \(a_1\) 时的应加次数升序排序
令 \(sum1\) 为 \(val1\) 的前缀和
就会发现当 \(a_1\) 增加 \(x\) 时可以在 \(val1\) 中二分出一个分界点 \(t\)
可以消掉的操作数就是 \(2(sum1_t+x(|A|-t))\)
点击查看代码
#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define N 200010
#define ll long long
//#define int long long
char buf[1<<21], *p1=buf, *p2=buf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf, 1, 1<<21, stdin)), p1==p2?EOF:*p1++)
inline int read() {
int ans=0, f=1; char c=getchar();
while (!isdigit(c)) {if (c=='-') f=-f; c=getchar();}
while (isdigit(c)) {ans=(ans<<3)+(ans<<1)+(c^48); c=getchar();}
return ans*f;
}
int n, q;
int a[N], b[N], t[N];
int cge[N], val1[N], val2[N], val3[N], val4[N], top1, top2, top3, top4;
ll sum1[N], sum2[N], sum3[N], sum4[N], sum, once=1, x;
bool ina[N], inb[N], inc[N], ind[N];
signed main()
{
n=read();
for (int i=1; i<=n; ++i) a[i]=read();
for (int i=1; i<=n; ++i) b[i]=read();
for (int i=2; i<=n; ++i) a[i]-=b[i];
for (int i=2; i<=n; ++i) if (a[i]) {
cge[i]=-a[i];
for (int j=i*2; j<=n; j+=i) a[j]-=a[i];
a[i]=0;
}
for (int i=2; i<=n; ++i) ++a[i];
for (int i=2; i<=n; ++i) if (a[i]) {
++once;
if (a[i]<0) ina[i]=1;
else inb[i]=1;
for (int j=i*2; j<=n; j+=i) a[j]-=a[i];
a[i]=0;
}
for (int i=1; i<=n; ++i) sum+=abs(cge[i]);
for (int i=1; i<=n; ++i)
if (ina[i]&&cge[i]<0) val1[++top1]=abs(cge[i]);
else if (ina[i]&&cge[i]>0) val3[++top3]=abs(cge[i]);
else if (inb[i]&&cge[i]>0) val2[++top2]=abs(cge[i]);
else if (inb[i]&&cge[i]<0) val4[++top4]=abs(cge[i]);
sort(val1+1, val1+top1+1); sort(val2+1, val2+top2+1);
sort(val3+1, val3+top3+1); sort(val4+1, val4+top4+1);
for (int i=1; i<=top1; ++i) sum1[i]=sum1[i-1]+val1[i];
for (int i=1; i<=top2; ++i) sum2[i]=sum2[i-1]+val2[i];
for (int i=1; i<=top3; ++i) sum3[i]=sum3[i-1]+val3[i];
for (int i=1; i<=top4; ++i) sum4[i]=sum4[i-1]+val4[i];
#if 0
cout<<"val1: "; for (int i=1; i<=top1; ++i) cout<<val1[i]<<' '; cout<<endl;
cout<<"val2: "; for (int i=1; i<=top2; ++i) cout<<val2[i]<<' '; cout<<endl;
cout<<"val3: "; for (int i=1; i<=top3; ++i) cout<<val3[i]<<' '; cout<<endl;
cout<<"val4: "; for (int i=1; i<=top4; ++i) cout<<val4[i]<<' '; cout<<endl;
cout<<"cge: "; for (int i=1; i<=n; ++i) cout<<cge[i]<<' '; cout<<endl;
#endif
q=read();
while (q--) {
x=a[1]-read();
if (x>0) {
int t1=upper_bound(val3+1, val3+top3+1, x)-val3-1;
int t2=upper_bound(val4+1, val4+top4+1, x)-val4-1;
// cout<<"once: "<<once<<endl;
// cout<<"sum: "<<sum<<endl;
// cout<<"t: "<<t1<<' '<<t2<<endl;
// cout<<sum3[t1]+(top3-t1)<<' '<<sum4[t2]+(top4-t2)<<endl;
printf("%lld\n", sum+1ll*x*once-2ll*(sum3[t1]+x*(top3-t1)+sum4[t2]+x*(top4-t2)));
}
else if (x<0) {
x=abs(x);
int t1=upper_bound(val1+1, val1+top1+1, x)-val1-1;
int t2=upper_bound(val2+1, val2+top2+1, x)-val2-1;
// cout<<"once: "<<once<<endl;
// cout<<"sum: "<<sum<<endl;
// cout<<"t: "<<t1<<' '<<t2<<endl;
printf("%lld\n", sum+1ll*x*once-2ll*(sum1[t1]+x*(top1-t1)+sum2[t2]+x*(top2-t2)));
}
else printf("%lld\n", sum);
}
return 0;
}