[数论记录]CFgym102354B. Yet Another Convolution

· · 个人记录

神仙题Orz

题目Link

题意 : 给出两个数组A,B

求C_k=\max\limits_{gcd(i,j)=k}^n|A_i-B_j|

首先|A_i-B_j|=\max(A_i-B_j,B_j-A_i),只需要正反做两遍取\max就好了。

我们又把B整体乘个-1,就变成C_k=\max\limits_{gcd(i,j)=k}^n(A_i+B_j)

看起来一脸不可做……

考虑到经典GCD卷积暴力做复杂度很优,我们也尝试暴力。

C_k=\max\limits_{k|i}^n(A_i+\max\limits_{gcd(i,j)=k}^nB_j) \max\limits_{k|i}^n(A_i+\max\limits_{k|j}^nB_j[(i,j)==k]) \max\limits_{i=1}^{n/k}(A_{ik}+\max\limits_{j=1}^{n/k}B_{jk}[i\perp j])

我们考虑对于每个k单独拖出来做。

可以看做这种子问题\max\limits_{i=1}^{m}(A_i+\max\limits_{j=1}^{m}B_j[i\perp j])

现在问题就变成了给定数组B若干个t快速查询\max\limits_{i=1}^{m}B_i[i\perp t]

这个\max十分讨厌,考虑二分转化成判定性问题,多组询问就考虑整体二分。

如果\sum\limits_{i=1}^{m}[C\leq B_i][i\perp t]>0,我们就能判定答案大于等于C

对于\sum我们就有很多玩法了:

=\sum\limits_{i=1}^{m}[C\leq B_i]\sum\limits_{d|t,d|i}\mu(d) =\sum\limits_{d|t}\mu(d)\sum\limits_{d|i}^{m}[C\leq B_i]

我们整体二分的时候,先把B离散化,然后按照如下流程分治:

这里我们需要一个数据结构,资瓷求某个数倍数处点权和,带修。

无脑写一个枚举约数就好了,修改O(d(i)),查询甚至O(1).

注意到,在分治树上,每个询问都要历经O(logm)次判别,每个B_i都会加入O(logm)次。

注意到每次判别都需要O(d(i))次查询,实际上,两部分复杂度同为O(logm*d(i))。

总的复杂度O(logm\sum\limits_{i=1}^md(i))=O(mlog^2m)

我们算一下总的复杂度 : O(\sum\limits_{k=1}^n(\frac{n}{k})log^2(\frac{n}{k}))=O(nlog^2n\sum\limits_{k=1}^n\frac{1}{k})=O(nlog^3n)

掐指一算,其中两个log都是调和级数,常数较小,6S 应该稳过……

代码细节比较少,还是很好写的。居然只跑了800ms……神了

#include<algorithm>
#include<cstring>
#include<cstdio>
#include<vector>
#define pf printf
#define INF 2000000000
#define MaxN 100500
using namespace std;
inline int read()
{
  register int X=0;
  register char ch=0;
  while(ch<48||ch>57)ch=getchar();
  while(ch>=48&&ch<=57)X=X*10+(ch^48),ch=getchar();
  return X;
}
vector<int> d[MaxN];
int n,mu[MaxN],p[MaxN],tn;
bool e[MaxN];
void sieve()
{
  mu[1]=1;
  for (int i=2;i<=n;i++){
    if (!e[i])mu[p[++tn]=i]=-1;
    for (int j=1,t;j<=tn&&(t=i*p[j])<=n;j++){
      e[t]=1;
      if (i%p[j]==0)break;
      mu[t]=-mu[i];
    }
  }
  for (int i=1;i<=n;i++)
    for (int j=1;i*j<=n;j++)
      d[i*j].push_back(i);
}
int tp[MaxN],xx[MaxN],s3[MaxN],q[MaxN];
int s1[MaxN],s2[MaxN],tc[MaxN];
void upd(int t,int c)
{
  for (int i=0;i<d[t].size();i++)
    tc[d[t][i]]+=c;
}
int qry(int t)
{
  int ret=0;
  for (int i=0;i<d[t].size();i++)
    ret+=mu[d[t][i]]*tc[d[t][i]];
  return ret;
}
void ltg(int tim)
{
  if (tn>tim)
    for (int i=tim;i<tn;i++)
      upd(tp[i],1);
  else
    for (int i=tn;i<tim;i++)
      upd(tp[i],-1);
  tn=tim;
}
int sq[MaxN];
void solve2(int l,int r,int tl,int tr)
{
  if (l>r)return ;
  if (tl==tr){
    for (int i=l;i<=r;i++)s3[q[i]]=tl;
    return ;
  }int tmid=(tl+tr)>>1,pl=l-1,pr=r+1;
  ltg(tmid+1);
  for (int i=l;i<=r;i++)
    if (qry(q[i])<=0)sq[++pl]=q[i];
    else sq[--pr]=q[i];
  memcpy(q+l,sq+l,sizeof(int)*(r-l+1));
  solve2(l,pl,tl,tmid);
  solve2(pr,r,tmid+1,tr);
}
int solve1(int m)
{
  memcpy(xx,s2,sizeof(int)*(m+5));
  sort(xx+1,xx+m+1);
  for (int i=1,sav;i<=m;i++){
    sav=upper_bound(xx+1,xx+m+1,s2[i])-xx-1;
    tp[sav]=i;xx[sav]++;
  }memset(tc,0,sizeof(int)*(m+5));tn=m+1;
  for (int i=1;i<=m;i++)q[i]=i;
  solve2(1,m,1,m);
  int ret=-INF;
  for (int i=1;i<=m;i++)
    ret=max(ret,s1[i]+xx[s3[i]]-1);
  return ret;
}
int a[MaxN],b[MaxN],ans[MaxN];
void solve0()
{
  for (int k=1;k<=n;k++){
    for (int i=1;i*k<=n;i++)
      {s1[i]=a[i*k];s2[i]=b[i*k];}
    ans[k]=max(ans[k],solve1(n/k));
  }
}
int main()
{
  scanf("%d",&n);
  sieve();
  for (int i=1;i<=n;i++)a[i]=read();
  for (int i=1;i<=n;i++)b[i]=-read();
  solve0();
  for (int i=1;i<=n;i++)
    {a[i]=-a[i];b[i]=-b[i];}
  solve0();
  for (int i=1;i<=n;i++)pf("%d ",ans[i]);
}