Harbour.Space Scholarship Contest 2021-2022 (open for everyone, rated, Div. 1 + Div. 2)
F. Pairwise Modulo
You have an array a consisting of n distinct positive integers, numbered from 1 to n. Define pk as
\[p_k=\sum_{1\le i,j\le k}a_i\ mod\ a_j
\]
You have to find and print p1,p2,…,pnp1,p2,…,pn.
\[2\le n \le 2*10^5,1\le a_i \le3*10^5,a_i\neq a_j,if\ i\neq\ j\\]
时限4s
\[首先考虑去拆a_i\ mod\ a_j\a_i\ mod\ a_j=a_i-\lfloor\frac{a_i}{a_j}\rfloor a_j\设sum_i为a_i的前缀和，ans_i为选了前i个的贡献
\\我们每加入一个新的数a_i会产生\sum_{j=1}^{i-1}(a_i-\lfloor\frac{a_i}{a_j}\rfloor a_j)
+\sum_{j=1}^{i-1}(a_j-\lfloor\frac{a_j}{a_i}\rfloor a_i)的贡献\对于后一部分只需分别统计在区间[0,a_i),[a_i,2a_i)\cdots中已被加入的数的个数\设上界为M那么每个数至多会统计\frac{M}{a_i}个区间，每个a_i都不相等，那么这里最坏情况为\\frac{M}{1}+\frac{M}{2}+\frac{M}{3}+\frac{M}{4}+\cdots\approx MlnM\区段内数的个数可以线段树或树状数组维护单次修改与查询复杂度O(logn)\后一部分总体复杂度O(MlnMlog
M)\\]
\[对前一部分，先提供一种假的做法，对一个新加入的b_i我们只用考虑\frac{b_i}{k}有多少种可能的结果\由数论分块可以求出有2\sqrt{b_i}种不同的结果，分别对这些区间内的数求和加到贡献中\区间内数的求和可以线段树或树状数组维护总体复杂度O(2M\sqrt{M}logM)\看起来4s的时限似乎能过,但实际上在我本地跑了6900ms，可能没有那个2的常数就能过\之后一直在尝试各种优化，但还是没卡过去（被4s的时限骗了，以为这个复杂度是对的）
放一下假的代码
\]
#include<bits/stdc++.h>
using namespace std;
const int maxn=300005;
//#define int long long
#define lowbit(x) x&(-x)
long long a1[500050];//树状数组
int a[500050];
int b[500100];
long long sum[500100];
long long ans[500000];
inline int read()
{
int res=0;
char c=getchar();
while(c<‘0‘||c>‘9‘)c=getchar();
while(c>=‘0‘&&c<=‘9‘)
{
res=(res<<1)+(res<<3)+c-‘0‘;
c=getchar();
}
return res;
}
void add(int x)
{
while(x<=maxn)
{
a[x]++;
x+=x&(-x);
}
}
int get(int x)
{
if(x<=0)return 0;
int ans=0;
while(x)
{
ans+=a[x];
x-=x&(-x);
}
return ans;
}
void add1(int x,int zhi)
{
while(x<=maxn)
{
a1[x]+=zhi;
x+=x&(-x);
}
}
long long get1(int x)
{
if(x<=0)return 0;
long long ans=0;
while(x)
{
ans+=a1[x];
x-=x&(-x);
}
return ans;
}
void print(long long x)
{
if(x>=10)print(x/10);
putchar(x%10+‘0‘);
}
signed main()
{
int ks=clock();
// freopen("std.in","r",stdin);
// freopen("std.out","w",stdout);
int n;
scanf("%d",&n);
int jx=0;
int timel=0;
for(int i=1;i<=n;i++)
{
b[i]=read();
sum[i]=sum[i-1]+b[i];
jx=max(jx,b[i]);
add(b[i]);
add1(b[i],b[i]);
int cnt=0;
int now=0;
for(int l=0,r;l<=jx;l=r+1)
{
if(now==i)break;
r=l+b[i]-1;
if(r>maxn)r=maxn;
int ans1=get(r)-get(l-1);
now+=ans1;
// timel++;
// cout<<l<<" "<<r<<" "<<get(l-1)<<" "<<get(r)<<"\n";
ans[i]-=1ll*b[i]*cnt*ans1;
cnt++;
}
now=0;
int limit=get1(b[i]-1);
int cs=0;
for(int l=1,r;l<=b[i];l=r+1)
{
if(now==limit)
{
cs=1;break;
}
r=b[i]/(b[i]/l);
int ans1=get1(r)-get1(l-1);
now+=ans1;
timel++;
// cout<<b[i]<<" "<<l<<" "<<r<<" "<<ans1<<"\n";
ans[i]-=1ll*b[i]/l*ans1;
}
ans[i]+=ans[i-1];
ans[i]+=sum[i-1];
ans[i]+=1ll*b[i]*i;
if(!cs)ans[i]+=b[i];
}
// for(int i=1;i<=n;i++)
// cout<<b[i]<<" ";cout<<"\n";
// for(int i=1;i<=n;i++)
// cout<<sum[i]<<" ";cout<<"\n";
for(int i=1;i<n;i++)
{
// printf("%lld ",ans[i]);
print(ans[i]);putchar(‘ ‘);
}
// printf("%lld\n",ans[n]);
print(ans[n]);putchar(‘\n‘);
int js=clock();
// cout<<ks-js<<"\n";
// cout<<timel<<"\n";
return 0;
}
\[之后看了官方题解，发现他对前一部分的处理是这样的\不考虑用a_i去找a_j，而是在前面加入a_j时就考虑对后面的贡献\如a_j加入后对区间[0,a_j)[a_j,2a_j)[2a_j,3a_j)\cdots的贡献分别为0，a_j,2a_j\cdots\和后一部分的方法类似没加入一个数后,将a_i,2a_i\cdots的位置加上a_i，这样在统计前缀和时对应区间的贡献就是ka_i\这样在新的a_i处的贡献可以直接求a_i的前缀和去解决\复杂度和前一部分类似都是调和级数求和加上区间求和的复杂度O(logn)，总体复杂度O(Mlog^2M)\最终在cf上只跑了358ms，远低于4000ms\粘一下代码
\]
#include<bits/stdc++.h>
using namespace std;
const int maxn=300005;
//#define int long long
#define lowbit(x) x&(-x)
long long a1[500050];//树状数组
int a[500050];
int b[500100];
long long sum[500100];
long long ans[500000];
inline int read()
{
int res=0;
char c=getchar();
while(c<‘0‘||c>‘9‘)c=getchar();
while(c>=‘0‘&&c<=‘9‘)
{
res=(res<<1)+(res<<3)+c-‘0‘;
c=getchar();
}
return res;
}
void add(int x)
{
while(x<=maxn)
{
a[x]++;
x+=x&(-x);
}
}
int get(int x)
{
if(x<=0)return 0;
int ans=0;
while(x)
{
ans+=a[x];
x-=x&(-x);
}
return ans;
}
void add1(int x,int zhi)
{
while(x<=maxn)
{
a1[x]+=zhi;
x+=x&(-x);
}
}
long long get1(int x)
{
if(x<=0)return 0;
long long ans=0;
while(x)
{
ans+=a1[x];
x-=x&(-x);
}
return ans;
}
void print(long long x)
{
if(x>=10)print(x/10);
putchar(x%10+‘0‘);
}
signed main()
{
int ks=clock();
// freopen("std.in","r",stdin);
// freopen("std.out","w",stdout);
int n;
scanf("%d",&n);
int jx=0;
int timel=0;
for(int i=1;i<=n;i++)
{
b[i]=read();
sum[i]=sum[i-1]+b[i];
jx=max(jx,b[i]);
add(b[i]);
for(int k=1;k*b[i]<=maxn;k++)
add1(k*b[i],b[i]);
int cnt=0;
int now=0;
for(int l=0,r;l<=jx;l=r+1)
{
if(now==i)break;
r=l+b[i]-1;
if(r>maxn)r=maxn;
int ans1=get(r)-get(l-1);
now+=ans1;
// timel++;
// cout<<l<<" "<<r<<" "<<get(l-1)<<" "<<get(r)<<"\n";
ans[i]-=1ll*b[i]*cnt*ans1;
cnt++;
}
now=0;
int cs=0;
int o=0;
ans[i]-=get1(b[i]);
// for(int l=1,r;l<=b[i];l=r+1)
// {
// if(now==limit)
// {
// cs=1;break;
// }
// r=b[i]/(b[i]/l);
// int ans1=get1(r)-get1(l-1);
// now+=ans1;
// o++;
//
// timel++;
//// cout<<b[i]<<" "<<l<<" "<<r<<" "<<ans1<<"\n";
// ans[i]-=1ll*b[i]/l*ans1;
// }printf("%d %d\n",b[i],o);
ans[i]+=ans[i-1];
ans[i]+=sum[i-1];
ans[i]+=1ll*b[i]*i;
if(!cs)ans[i]+=b[i];
}
// for(int i=1;i<=n;i++)
// cout<<b[i]<<" ";cout<<"\n";
// for(int i=1;i<=n;i++)
// cout<<sum[i]<<" ";cout<<"\n";
for(int i=1;i<n;i++)
{
printf("%lld ",ans[i]);
// print(ans[i]);putchar(‘ ‘);
}
printf("%lld\n",ans[n]);
// print(ans[n]);putchar(‘\n‘);
// int js=clock();
// cout<<ks-js<<"\n";
// cout<<timel<<"\n";
return 0;
}