二次离线莫队
二次离线莫队的做法参考第十四分块（前体）的题解
我们需要考虑从(1,i)如何推到(1,i+1)
我们算过了a[i]的答案，考虑加入a[i]的贡献
我们需要在a[i]的所有约数上打标记，这个珂以直接暴力（因为约数是\(\sqrt n\)级别的）
我们还要考虑倍数的问题，当a[i]>32时，直接暴力更新倍数打标记；a[i]<=32时，设计一个状态s[1……32]，每位1表示有这个约数，0表示没有这个约数，因为一共232个状态过多，所以每8个拆成一位，变成4个28=256状态，我们需要在0~255中第a[i]%8位为1的状态打标记即可
说的有可能不清楚，放一下代码
inline void update(register int x)
{
for(register int i=0;i<tot[x];++i)
++bs[fac[x][i]];
if(x<=32)
{
if(x<=8)
{
for(register int s=0;s<256;++s)
if(s>>(x-1)&1)
++s1[s];
}
else if(x<=16)
{
for(register int s=0;s<256;++s)
if(s>>(x-9)&1)
++s2[s];
}
else if(x<=24)
{
for(register int s=0;s<256;++s)
if(s>>(x-17)&1)
++s3[s];
}
else
{
for(register int s=0;s<256;++s)
if(s>>(x-25)&1)
++s4[s];
}
}
else
for(register int i=x;i<=100000;i+=x)
++ys[i];
}
我们考虑a[i+1]的答案，答案就是约数标记、倍数标记和状压标记之和。状压标记要单独计算（如下），c[x]就是一个长为32位的状态，表示x是否有1~32的约数
inline int calc(register unsigned int x)
{
x=c[x];
return s1[x&255]+s2[x>>8&255]+s3[x>>16&255]+s4[x>>24];
}
完整代码（有些我可能说不清，珂以结合代码理解）
#include <bits/stdc++.h>
#define N 100005
#define ll long long
#define getchar nc
using namespace std;
inline char nc(){
static char buf[100000],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int read()
{
register int x=0,f=1;register char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return x*f;
}
inline void write(register ll x)
{
if(!x)putchar('0');if(x<0)x=-x,putchar('-');
static int sta[20];register int tot=0;
while(x)sta[tot++]=x%10,x/=10;
while(tot)putchar(sta[--tot]+48);
}
int n,m,a[N],blocksize,s1[256],s2[256],s3[256],s4[256];
struct query{
int l,r,id,bl;
}q[N];
inline bool cmp(register query a,register query b)
{
return a.bl!=b.bl?a.l<b.l:((a.bl&1)?a.r<b.r:a.r>b.r);
}
int fac[N][200],tot[N],ys[N],bs[N];
unsigned int c[N];
ll pres[N],sufs[N],ans[N],res[N];
struct node{
int l,r,id,op;
};
vector<node> L[N],R[N];
inline int calc(register unsigned int x)
{
x=c[x];
return s1[x&255]+s2[x>>8&255]+s3[x>>16&255]+s4[x>>24];
}
inline void update(register int x)
{
for(register int i=0;i<tot[x];++i)
++ys[fac[x][i]];
if(x<=32)
{
if(x<=8)
{
for(register int s=0;s<256;++s)
if(s>>(x-1)&1)
++s1[s];
}
else if(x<=16)
{
for(register int s=0;s<256;++s)
if(s>>(x-9)&1)
++s2[s];
}
else if(x<=24)
{
for(register int s=0;s<256;++s)
if(s>>(x-17)&1)
++s3[s];
}
else
{
for(register int s=0;s<256;++s)
if(s>>(x-25)&1)
++s4[s];
}
}
else
for(register int i=x;i<=100000;i+=x)
++bs[i];
}
inline void clear()
{
memset(s1,0,sizeof(s1));
memset(s2,0,sizeof(s2));
memset(s3,0,sizeof(s3));
memset(s4,0,sizeof(s4));
memset(ys,0,sizeof(ys));
memset(bs,0,sizeof(bs));
}
int main()
{
for(register int i=1;i<=100000;++i)
{
for(register int j=i;j<=100000;j+=i)
fac[j][tot[j]++]=i;
if(i<=32)
for(register int j=i;j<=100000;j+=i)
c[j]|=1u<<i-1;
}
n=read(),m=read();
blocksize=n/(sqrt(m*2/3)+1);
for(register int i=1;i<=n;++i)
a[i]=read();
for(register int i=1;i<=m;++i)
{
int l=read(),r=read();
q[i]=(query){l,r,i,(l-1)/blocksize+1};
}
sort(q+1,q+1+m,cmp);
for(register int i=1;i<=n;++i)
{
pres[i]=pres[i-1]+ys[a[i]]+bs[a[i]]+calc(a[i]);
update(a[i]);
}
clear();
for(register int i=n;i>=1;--i)
{
sufs[i]=sufs[i+1]+ys[a[i]]+bs[a[i]]+calc(a[i]);
update(a[i]);
}
clear();
q[0].l=1,q[0].r=0;
for(register int i=1;i<=m;++i)
{
int pl=q[i-1].l,pr=q[i-1].r,nl=q[i].l,nr=q[i].r;
ans[i]=pres[nr]-pres[pr]+sufs[nl]-sufs[pl];
if(nr>pr)
R[pl-1].push_back((node){pr+1,nr,i,-1});
if(nr<pr)
R[pl-1].push_back((node){nr+1,pr,i,1});
if(nl<pl)
L[nr+1].push_back((node){nl,pl-1,i,-1});
if(nl>pl)
L[nr+1].push_back((node){pl,nl-1,i,1});
}
for(register int i=1;i<=n;++i)
{
update(a[i]);
for(register int j=0;j<R[i].size();++j)
{
int l=R[i][j].l,r=R[i][j].r;
ll tmp=0;
for(register int k=l;k<=r;++k)
tmp+=ys[a[k]]+bs[a[k]]+calc(a[k]);
ans[R[i][j].id]+=tmp*R[i][j].op;
}
}
clear();
for(register int i=n;i>=1;--i)
{
update(a[i]);
for(register int j=0;j<L[i].size();++j)
{
int l=L[i][j].l,r=L[i][j].r;
ll tmp=0;
for(register int k=l;k<=r;++k)
tmp+=ys[a[k]]+bs[a[k]]+calc(a[k]);
ans[L[i][j].id]+=tmp*L[i][j].op;
}
}
for(register int i=1;i<=m;++i)
ans[i]+=ans[i-1],res[q[i].id]=ans[i]+q[i].r-q[i].l+1;
for(register int i=1;i<=m;++i)
write(res[i]),puts("");
return 0;
}
