[DS记录]P5398 [Ynoi2018] GOSICK
command_block
2021-07-02 11:53:42
第十四分块。
**题意** ： 给出一个长度为 $n$ 的序列 $A$。
每次询问给出 $l,r$ ，求 $l \leq i,j\leq r$，且 $A_i$ 是 $A_j$ （非严格）倍数的二元组 $(i,j)$ 的个数。
（不要求 $i\neq j$ ， $(i,j)$ 和 $(j,i)$ 算两个不同的二元组）
允许离线， $n,m,A_i\leq 5\times 10^5$ ，时限$\texttt{3s}$，空限$\texttt{128M}$。
------------
认为 $n,m,A$ 同阶。
二次离线莫队。
先不考虑 $i=j$ 的 $(i,j)$ 的贡献，最后再将答案加上 $r-l+1$。
考虑从区间 $[l+1,r]$ 移动到 $[l,r]$ ，贡献的变化量为：
$$\sum\limits_{l<i\leq r}[A_l|A_i]+[A_i|A_l]$$
可以差分为
$$\sum\limits_{i\leq r}[A_p|A_i]+\sum\limits_{i\leq r}[A_i|A_p]$$
分因数，倍数两部分处理。
- 倍数查询
维护 $w_x$ 表示目前为 $x$ 的倍数的数的个数。
插入一个数的复杂度为 $O(d(n))$ ，查询为 $O(1)$ ，套用二次离线即可做到 $O\Big(n\big(d(n)+\sqrt{n}\big)\Big)=O(n\sqrt{n})$。
- 因数查询
维护 $w_x$ 表示目前为 $x$ 的因数的数的个数。
插入数 $x$ 的复杂度为 $O(n/x)$ 。
考虑根号分治，对于 $>\sqrt{n}$ 的数，插入复杂度 $\leq O(\sqrt{n})$，用二次离线莫队处理。这部分复杂度为 $O(n\sqrt{n})$。
对于剩下 $\leq \sqrt{n}$ 的数，不在莫队中处理（莫队中只保留 $>\sqrt{n}$ 的数），分别直接考虑对询问的贡献。
数 $x$ 在询问 $[l,r]$ 中的贡献为 ：
$$
\begin{aligned}
&\sum\limits_{l\leq i,j\leq r}[A_i=x][x|A_j]\\
=&\sum\limits_{l\leq i\leq r}[A_i=x]\sum\limits_{l\leq i\leq r}[x|A_i]\\
\end{aligned}
$$
只要知道 $[A_i=x]$ 与 $[x|A_i]$ 的区间和即可计算。对于每个 $x$ 分别处理区间和，然后贡献即可。
这部分的复杂度也是为 $O(n\sqrt{n})$ 。
一些卡常小技巧：
- 对于数 $x$ ，若 $cnt_x*A/x>n$ 则特殊处理，反之用莫队处理。（代替根号分治无脑选 $\sqrt{n}$ 以下的策略）
- 用 `vector` （或者压紧的数组）预处理每个数的约数。无需考虑特殊处理的数。
本来以为会很卡常，结果区区几发就过了，还是最优解……
```cpp
#include<algorithm>
#include<cstdio>
#include<vector>
#include<cmath>
#define ll long long
#define pb emplace_back
#define MaxN 500500
using namespace std;
namespace io {}using namespace io;
int lim,o[MaxN],d[MaxN<<4],pd[MaxN];bool fl[MaxN];
void InitD(int cost)
{
for (int i=1;i<=lim;i++)
fl[i]=(1ll*o[i]*lim/i>cost)||!o[i];
for (int i=1;i<=lim;i++)if (!fl[i])
for (int j=i;j<=lim;j+=i)if (!fl[i])
pd[j]++;
for (int i=1;i<=lim;i++)pd[i]+=pd[i-1];
for (int i=1;i<=lim;i++)if (!fl[i])
for (int j=i;j<=lim;j+=i)if (!fl[i])
d[++pd[j-1]]=i;
for (int i=lim;i;i--)pd[i]=pd[i-1];pd[0]=0;
}
int t[MaxN];
inline void add(int x){
for (int i=pd[x-1]+1;i<=pd[x];i++)t[d[i]]++;
for (int i=x;i<=lim;i+=x)t[i]++;
}
struct Data{int l,r,p;};
Data b[MaxN];int BS;
bool cmp(const Data &A,const Data &B)
{return A.l/BS==B.l/BS ? (A.l/BS)&1 ? A.r<B.r : A.r>B.r : A.l<B.l;}
vector<Data> bl[MaxN],br[MaxN];
ll ans[MaxN];int sav[MaxN];
int n,m,a[MaxN];
void MoQ()
{
BS=n/sqrt(m)+1;
sort(b+1,b+m+1,cmp);
int l=1,r=0;
for (int i=1;i<=m;i++){
if (b[i].l>b[i].r)continue;
if (b[i].l<l){bl[r].pb((Data){b[i].l,l-1,b[i].p});l=b[i].l;}
if (r<b[i].r){br[l].pb((Data){r+1,b[i].r,b[i].p});r=b[i].r;}
if (l<b[i].l){bl[r].pb((Data){l,b[i].l-1,-b[i].p});l=b[i].l;}
if (b[i].r<r){br[l].pb((Data){b[i].r+1,r,-b[i].p});r=b[i].r;}
}
#define ad(p,x) if (p<0)ans[-p]-=x;else ans[p]+=x;
for (int i=1;i<=n;i++){
for (int j=0;j<br[i].size();j++){
Data &now=br[i][j];ll ret=0;
for (int r=now.l;r<=now.r;r++)ret-=t[a[r]];
ad(now.p,ret);
}
add(a[i]);sav[i]=t[a[i]];
for (int j=0;j<bl[i].size();j++){
Data &now=bl[i][j];ll ret=0;
for (int l=now.l;l<=now.r;l++)ret+=t[a[l]]-sav[l];
ad(now.p,ret);
}
}
for (int i=1;i<=n;i++)
for (int j=0;j<br[i].size();j++){
Data &now=br[i][j];ll ret=0;
for (int r=now.l;r<=now.r;r++)ret+=sav[r]-2;
ad(now.p,ret);
}
for (int i=1;i<=m;i++)ans[b[i].p]+=ans[b[i-1].p];
for (int i=1;i<=m;i++)
if (b[i].l<=b[i].r)ans[b[i].p]+=b[i].r-b[i].l+1;
else ans[b[i].p]=0;
}
int n0,a0[MaxN],tp[MaxN],s1[MaxN],s2[MaxN];
ll ans2[MaxN];
int main()
{
n0=rd();m=rd();
for (int i=1;i<=n0;i++){
o[a0[i]=rd()]++;
lim=max(lim,a0[i]);
}
InitD((n0+m)*3);
for (int i=1;i<=n0;i++){
if (!fl[a0[i]])a[++n]=a0[i];
tp[i]=n;
}
for (int i=1;i<=m;i++)
{b[i].l=rd()-1;b[i].r=rd();}
for (int x=1;x<=lim;x++)if (fl[x]&&o[x]){
for (int i=1;i<=n0;i++){
s1[i]=s1[i-1]+(a0[i]==x);
s2[i]=s2[i-1]+(a0[i]%x==0);
}
for (int i=1;i<=m;i++)
ans2[i]+=1ll*(s1[b[i].r]-s1[b[i].l])*(s2[b[i].r]-s2[b[i].l]);
}
for (int i=1;i<=m;i++){
b[i].l=tp[b[i].l]+1;
b[i].r=tp[b[i].r];
b[i].p=i;
}
MoQ();
for (int i=1;i<=m;i++)print(ans[i]+ans2[i]),putc('\n');
flush();
return 0;
}
```