二次离线莫队

二次离线莫队的做法参考第十四分块（前体）的题解

我们需要考虑从(1,i)如何推到(1,i+1)

我们算过了a[i]的答案，考虑加入a[i]的贡献

我们需要在a[i]的所有约数上打标记，这个珂以直接暴力（因为约数是\(\sqrt n\)级别的）

我们还要考虑倍数的问题，当a[i]>32时，直接暴力更新倍数打标记；a[i]<=32时，设计一个状态s[1……32]，每位1表示有这个约数，0表示没有这个约数，因为一共2^32个状态过多，所以每8个拆成一位，变成4个2^8=256状态，我们需要在0~255中第a[i]%8位为1的状态打标记即可

说的有可能不清楚，放一下代码

inline void update(register int x){    for(register int i=0;i
    
     >(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 
    
     #define N 100005#define ll long long#define getchar ncusing 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.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
       
         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
        
         >(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<
         
          =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
          
           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
           
            =1;--i) { update(a[i]); for(register int j=0;j