#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
#define inf 0x3f3f3f3f
#define ll long long
#define maxn 100100
struct node{
ll v,w;
}a[maxn],b[maxn],a1[maxn],a2[maxn],b1[maxn],b2[maxn];
ll tempa[maxn],tempb[maxn];
vector<int>yz[maxn];
int vis[maxn],prime[maxn],mu[maxn];
void inite(){
for(int i=1;i<maxn;i++){
for(int j=i;j<maxn;j=j+i){
yz[j].push_back(i);
}
}
int cnt=0;
mu[1]=1;
for(int i=2;i<maxn;i++){
if(vis[i]==0){
prime[++cnt]=i;
mu[i]=-1;
}
for(int j=1;j<=cnt&&i*prime[j]<maxn;j++){
vis[i*prime[j]]=1;
if(i%prime[j]==0){
mu[i*prime[j]]=0;
break;
}
mu[i*prime[j]]=-mu[i];
}
}
}
ll ans[maxn];
int temp1[maxn],temp2[maxn];
ll get1(int la,int ra,int lb,int rb,int l,int r){
//printf("%d %d %d %d %d %d\n",la,ra,lb,rb,l,r);
if(la>ra||lb>rb||l>r)return 0;
if(l==r){
ll res=0;
for(int i=la;i<=ra;i++){
res=max(res,abs(l-a[i].v));
}
//printf("%lld\n",res);
return res;
}
int m=(l+r)/2;
int zb=0,yb=0;
for(int i=lb;i<=rb;i++){
if(b[i].v<=m){
//printf("000\n");
b1[++zb]=b[i];
//printf("%d %d\n",b[i].w,yz[b[i].w].size());
for(int j=0;j<yz[b[i].w].size();j++){
temp1[yz[b[i].w][j]]+=mu[yz[b[i].w][j]];
//printf("%d %d\n",temp1[yz[b[i].w][j]],mu[yz[b[i].w][j]]);
}
}
else{
b2[++yb]=b[i];
}
}
for(int i=lb;i<=lb+zb-1;i++)b[i]=b1[i-lb+1];
for(int i=lb+zb;i<=rb;i++)b[i]=b2[i-(lb+zb-1)];
int za=0,ya=0;
for(int i=la;i<=ra;i++){
int sum=0;
for(int j=0;j<yz[a[i].w].size();j++)sum+=temp1[yz[a[i].w][j]];
//printf("%d %d\n",i,sum);
if(sum)a1[++za]=a[i];
else a2[++ya]=a[i];
}
for(int i=la;i<=la+za-1;i++)a[i]=a1[i-la+1];
for(int i=la+za;i<=ra;i++)a[i]=a2[i-(la+za-1)];
for(int i=1;i<=zb;i++){
for(int j=0;j<yz[b1[i].w].size();j++)temp1[yz[b1[i].w][j]]-=mu[yz[b1[i].w][j]];
}
ll res=max(get1(la,la+za-1,lb,lb+zb-1,l,m),get1(la+za,ra,lb+zb,rb,m+1,r));
return res;
}
ll get2(int la,int ra,int lb,int rb,int l,int r){
if(la>ra||lb>rb||l>r)return 0;
if(l==r){
ll res=0;
for(int i=la;i<=ra;i++){
res=max(res,abs(l-a[i].v));
}
return res;
}
int m=(l+r)/2;
int zb=0,yb=0;
for(int i=lb;i<=rb;i++){
if(b[i].v>m){
b2[++yb]=b[i];
for(int j=0;j<yz[b[i].w].size();j++)temp1[yz[b[i].w][j]]+=mu[yz[b[i].w][j]];
}
else{
b1[++zb]=b[i];
}
}
for(int i=lb;i<=lb+zb-1;i++)b[i]=b1[i-lb+1];
for(int i=lb+zb;i<=rb;i++)b[i]=b2[i-(lb+zb-1)];
int za=0,ya=0;
for(int i=la;i<=ra;i++){
int sum=0;
for(int j=0;j<yz[a[i].w].size();j++)sum+=temp1[yz[a[i].w][j]];
if(sum)a2[++ya]=a[i];
else a1[++za]=a[i];
}
for(int i=la;i<=la+za-1;i++)a[i]=a1[i-la+1];
for(int i=la+za;i<=ra;i++)a[i]=a2[i-(la+za-1)];
for(int i=1;i<=yb;i++){
for(int j=0;j<yz[b2[i].w].size();j++)temp1[yz[b2[i].w][j]]-=mu[yz[b2[i].w][j]];
}
ll res=max(get2(la,la+za-1,lb,lb+zb-1,l,m),get2(la+za,ra,lb+zb,rb,m+1,r));
return res;
}
int main(){
inite();
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%lld",&tempa[i]);
for(int i=1;i<=n;i++)scanf("%lld",&tempb[i]);
for(int i=1;i<=n;i++){
for(int j=i;j<=n;j=j+i)a[j/i]=(node){tempa[j],j/i};
for(int j=i;j<=n;j=j+i)b[j/i]=(node){tempb[j],j/i};
ans[i]=max(ans[i],get1(1,n/i,1,n/i,0,inf));
//printf("%lld ",ans[i]);
ans[i]=max(ans[i],get2(1,n/i,1,n/i,0,inf));
printf("%lld",ans[i]);
if(i==n)printf("\n");
else printf(" ");
}
}
CFGym 102354B Yet Another Convolution（整体二分+莫比乌斯函数）
原文：https://www.cnblogs.com/League-of-cryer/p/14190888.html