二次离线莫队学习笔记
二次离线莫队
算法提出
二次离线莫队是一个由 lxl 大佬提出的新科技，其基于莫队 \(+\) 扫描线的思想，通过扫描线，再次将更新答案的过程离线处理，降低时间复杂度。
具体地，设更新答案的复杂度为 \(\mathcal O(k)\)，那么它可以将莫队的复杂度从 \(\mathcal O(nk\sqrt n)\) 降到了 \(\mathcal O(nk+n\sqrt n)\)， 大大简化了计算。
再补充一点，二次离线莫队通常适用于满足以下条件的题目：
- 可用莫队做。
- 莫队扩展或者删除一个点对答案的影响取决于当前区间的长度。
- 扩展或者删除一个点对答案的影响可用前缀写成差分的形式。
算法解决
以 模板题 为例。
给了你一个序列 \(a\)，每次查询给一个区间 \([l,r]\)，查询 \(l \leq i< j \leq r\)，且 \(a_i \oplus a_j\) 的二进制表示下有 \(k\) 个 \(1\) 的二元组 \((i,j)\) 的个数。
\(1 \leq n,m\leq10^5,0 \leq a_i,k < 16384\)，时限 \(1 \text{s}\)，空限 \(500\text{MB}\)。
首先明确，这题如果用普通莫队的话，每一次移动指针的时候需要用 \(\mathcal O(C_{14}^k)\) 的复杂度来转移，显然过不去，于是考虑二次离线莫队。
设 \(a_x\) 对区间 \([l,r]\) 的贡献为 \(f(x,[l,r])\)。
我们考虑区间端点变化对答案的影响，以 \([l,r]\) 变成 \([l,r+k]\) 为例，答案增加了 \(\sum\limits_{i=r+1}^{r+k}f(i,[l,i-1])\)。
我们发现，\(f(i,[l,i-1])\) 可以差分成 \(f(i,[1,i-1])-f(i,[1,l-1])\)。
这样转移区间的贡献就分为两类：
- 一个前缀和它后面一个数的贡献，这可以预处理出来。
- 区间 \([r+1,r+k]\) 对前缀 \([1,l-1]\) 的贡献，保存下来用扫描线做即可。
对于其他情况，大力讨论即可，下面给出结论：
- 右端点右移，\([l,r]\) 变成 \([l,r+k]\)，答案增加了\(\sum\limits_{i=r+1}^{r+k}f(i,[1,i-1])-f(i,[1,l-1])\)。
- 右端点左移，\([l,r]\) 变成 \([l,r-k]\)，答案减少了 \(\sum\limits_{i=r-k+1}^{r}f(i,[1,i-1])-f(i,[1,l-1])\)。
- 左端点右移，\([l,r]\) 变成 \([l+k,r]\)，答案减少了 \(\sum\limits_{i=l}^{l+k-1}f(i,[1,r])-f(i,[1,i])\)。
- 左端点左移，\([l,r]\) 变成 \([l-k,r]\)，答案增加了 \(\sum\limits_{i=l-k}^{l-1}f(i,[1,r])-f(i,[1,i])\)。
再看扫描线部分。
我们对于每个前缀 \([1,i]\) 开一个 vector，其中装二元组 \((l_0,r_0)\)（对应上面的 \([r+1,r+k]\)）（另外还要装一个 \(id\)，如果 \(id<0\)，代表减法，否则代表加法，贡献加到 \(\mid i \mid\) 这里去）。
假设当前前缀为 \([1,i]\)，二元组为 \((l_0,r_0)\)，设 \(t[z]\) 表示当前前缀中的数异或 \(z\) 后得到的数恰好有 \(k\) 个 \(1\) 的数的个数。
再根据异或的一个性质：若 \(a\oplus b=c\)，则有 \(b \oplus c=a,a \oplus c=b\)。
所以插入一个 \(p\) 值时，就 \(\mathcal O(C_{14}^{k})\) 枚举所有二进制表示下有 \(k\) 个 \(1\) 的数 \(val\)，然后令 \(t[p \oplus val]++\) 即可（第一类贡献的预处理也用这种方法）。
询问时答案即为 \(\sum\limits_{i=l_0}^{r_o}t[i]\)。
对于 \(f(i,[1,i])\)，由于 \(i \oplus i=0\) 且 \(i=j\) 这个贡献不算，这可以转为 \(f(i,[1,i-1])\)，再加个特判即可。
由于第二类贡献需要先跑一次莫队记录 \(l_0,r_0\)（顺便加上第一类贡献），然后再跑一次扫描线计算，相当于再次离线，所以我们通常称以上算法为二次离线莫队。
可以发现，莫队部分时间复杂度为 \(\mathcal O(n\sqrt n)\)，当然也可以前缀和优化成 \(\mathcal O(n)\)，扫描线部分时间复杂度为 \(\mathcal O(n\sqrt n+n C_{14}^k)\)，所以总时间复杂度为 \(\mathcal O(n\sqrt n+n C_{14}^k)\)，可过。
\(\text{659ms / 15.43MB / 3.20KB C++20 O2}\)。
#include
using namespace std;
#define re register
namespace Fread
{
const int SIZE = 1 << 23;
char buf[SIZE], *S, *T;
inline char getchar()
{
if (S == T)
{
T = (S = buf) + fread(buf, 1, SIZE, stdin);
if (S == T)
return '\n';
}
return *S++;
}
}
namespace Fwrite
{
const int SIZE = 1 << 23;
char buf[SIZE], *S = buf, *T = buf + SIZE;
inline void flush()
{
fwrite(buf, 1, S - buf, stdout);
S = buf;
}
inline void putchar(char c)
{
*S++ = c;
if (S == T)
flush();
}
struct NTR
{
~NTR()
{
flush();
}
} ztr;
}
#ifdef ONLINE_JUDGE
#define getchar Fread::getchar
#define putchar Fwrite::putchar
#endif
typedef long long ll;
inline int read()
{
re int x = 0, f = 1;
re char c = getchar();
while (c < '0' || c > '9')
{
if (c == '-')
f = -1;
c = getchar();
}
while (c >= '0' && c <= '9')
{
x = x * 10 + c - '0';
c = getchar();
}
return x * f;
}
inline void write(re ll x)
{
if (x < 0)
{
putchar('-');
x = -x;
}
if (x > 9)
write(x / 10);
putchar(x % 10 + '0');
}
const int _ = 1e5 + 7;
int n, m, k, a[_], S, bel[_], t[_], pre[_];
ll Ans[_];
struct Query
{
int l, r, id;
ll ans;
inline bool operator < (const Query& tmp)
{
return bel[l] == bel[tmp.l] ? r < tmp.r : l < tmp.l;
}
} q[_];
vector> v[_];
signed main()
{
n = read(), m = read(), k = read();
S = sqrt(n);
if(k > 14)
{
for(re int i = 1; i <= m; ++i) putchar('0'), putchar('\n');
return 0;
}
for(re int i = 1; i <= n; ++i) a[i] = read();
for(re int i = 1; i <= m; ++i)
{
q[i].l = read();
q[i].r = read();
q[i].id = i;
}
vector b;
for(re int i = 0; i < 16384; ++i)
if(__builtin_popcount(i) == k) b.push_back(i);
for(re int i = 1; i <= n; ++i) bel[i] = (i - 1) / S + 1;
sort(q + 1, q + m + 1);
for(re int i = 1; i <= n; ++i)
{
for(re auto x : b) ++t[a[i] ^ x];
pre[i] = t[a[i + 1]];
}
memset(t, 0, sizeof t);
for(re int i = 1, l = 1, r = 0; i <= m; ++i)
{
if(l < q[i].l) v[r].emplace_back(l, q[i].l - 1, -i);
while(l < q[i].l)
{
q[i].ans += pre[l - 1];
++l;
}
if(l > q[i].l) v[r].emplace_back(q[i].l, l - 1, i);
while(l > q[i].l)
{
q[i].ans -= pre[l - 2];
--l;
}
if(r < q[i].r) v[l - 1].emplace_back(r + 1, q[i].r, -i);
while(r < q[i].r)
{
q[i].ans += pre[r];
++r;
}
if(r > q[i].r) v[l - 1].emplace_back(q[i].r + 1, r, i);
while(r > q[i].r)
{
q[i].ans -= pre[r - 1];
--r;
}
}
for(re int i = 1, id, l, r; i <= n; ++i)
{
for(re auto x : b) ++t[a[i] ^ x];
for(re const auto& x : v[i])
{
tie(l, r, id) = x;
for(re int j = l, tmp = 0; j <= r; ++j)
{
tmp = t[a[j]];
if(j <= i && k == 0) --tmp;
if(id < 0) q[-id].ans -= tmp;
else q[id].ans += tmp;
}
}
}
for(re int i = 1; i <= m; ++i) q[i].ans += q[i - 1].ans;
for(re int i = 1; i <= m; ++i) Ans[q[i].id] = q[i].ans;
for(re int i = 1; i <= m; ++i) write(Ans[i]), putchar('\n');
}
例题选讲
P5047 [Ynoi2019 模拟赛] Yuno loves sqrt technology II
给你一个长为 \(n\) 的序列 \(a\)，\(m\) 次询问，每次查询一个区间的逆序对数，不强制在线。
\(1 \leq n,m\leq 10^5,0 \leq a_i \leq 10^9\)，时限 \(250\text{ms}\)，空限 \(31.25\text{MB}\)。
首先明确，空限要求 \(\mathcal O(n)\)。
\(\mathcal O(n \sqrt n \log n)\) 应该谁都会做，而且谁都知道被卡了。
考虑二次离线莫队。
前面的差分都不讲了。
对于第一类贡献，预处理即可。
对于第二类贡献，这里跟上面那题稍微有些不同，就是左端点移动的话答案变化量就是比这个数小的数的个数，右端点移动的话答案变化量就是比这个数大的数的个数。
由于第二类贡献如果用树状数组 \(\mathcal O(\log n)\) 修改，\(\mathcal O(\log n)\) 查询的话，时间复杂度是 \(\mathcal O(n\log n+n \sqrt n \log n)\) 的，过不去。
由于瓶颈在于查询，考虑值域分块维护前缀和，\(\mathcal O(\sqrt n)\) 修改，\(\mathcal O(1)\) 查询，这样时间复杂度是 \(\mathcal O(n \sqrt n+n\sqrt n)\)，可过。
再加上莫队\(\mathcal O(n \sqrt n)\) 的复杂度。
总时间复杂度为 \(\mathcal O(n \sqrt n)\)，可过。
\(\text{ 956ms / 19.04MB / 3.56KB C++11 O2}\)。
#include
using namespace std;
#define re register
namespace Fread
{
const int SIZE = 1 << 23;
char buf[SIZE], *S, *T;
inline char getchar()
{
if (S == T)
{
T = (S = buf) + fread(buf, 1, SIZE, stdin);
if (S == T)
return '\n';
}
return *S++;
}
}
namespace Fwrite
{
const int SIZE = 1 << 23;
char buf[SIZE], *S = buf, *T = buf + SIZE;
inline void flush()
{
fwrite(buf, 1, S - buf, stdout);
S = buf;
}
inline void putchar(char c)
{
*S++ = c;
if (S == T)
flush();
}
struct NTR
{
~NTR()
{
flush();
}
} ztr;
}
#ifdef ONLINE_JUDGE
#define getchar Fread::getchar
#define putchar Fwrite::putchar
#endif
typedef long long ll;
inline int read()
{
re int x = 0, f = 1;
re char c = getchar();
while (c < '0' || c > '9')
{
if (c == '-')
f = -1;
c = getchar();
}
while (c >= '0' && c <= '9')
{
x = x * 10 + c - '0';
c = getchar();
}
return x * f;
}
inline void write(re ll x)
{
if (x < 0)
{
putchar('-');
x = -x;
}
if (x > 9)
write(x / 10);
putchar(x % 10 + '0');
}
const int _ = 1e5 + 7;
int n, m, k, a[_], c[_], S, bel[_], t[_], pre[_], pree[_], f1[_], f2[_], L[_], R[_], V;
ll Ans[_];
struct Query
{
int l, r, id;
ll ans;
inline bool operator < (const Query& tmp)
{
return bel[l] == bel[tmp.l] ? r < tmp.r : l < tmp.l;
}
} q[_];
vector> v[_];
void init()
{
memset(pre, 0, sizeof pre);
memset(pree, 0, sizeof pree);
}
void update(int x)
{
for(re int i = bel[x] + 1; i <= bel[V]; ++i) pre[i]++;
for(re int i = x + 1; i <= R[bel[x]]; ++i) pree[i]++;
}
int query(int x)
{
return pre[bel[x]] + pree[x];
}
signed main()
{
n = read(), m = read();
for(re int i = 1; i <= n; ++i) c[i] = a[i] = read();
sort(c + 1, c + n + 1);
re int un = unique(c + 1, c + n + 1) - c - 1;
for(int i = 1; i <= n; ++i)
{
a[i] = lower_bound(c + 1, c + un + 1, a[i]) - c;
V = max(V, a[i]);
}
S = sqrt(V);
for(re int i = 1; i <= m; ++i)
{
q[i].l = read();
q[i].r = read();
q[i].id = i;
}
for(re int i = 1; i <= V + 1; ++i) bel[i] = (i - 1) / S + 1;
for(re int i = 1; i <= bel[V + 1]; ++i) L[i] = R[i - 1] + 1, R[i] = i * S;
R[bel[V + 1]] = V + 1;
sort(q + 1, q + m + 1);
for(re int i = 1; i <= n; ++i)
{
f2[i] = i - query(a[i] + 1) - 1;
f1[i] = query(a[i]);
update(a[i]);
}
init();
for(re int i = 1, l = 1, r = 0; i <= m; ++i)
{
if(l < q[i].l) v[r].emplace_back(l, q[i].l - 1, -i, 0);
while(l < q[i].l)
q[i].ans += f1[l++];
if(l > q[i].l) v[r].emplace_back(q[i].l, l - 1, i, 0);
while(l > q[i].l)
q[i].ans -= f1[--l];
if(r < q[i].r) v[l - 1].emplace_back(r + 1, q[i].r, -i, 1);
while(r < q[i].r)
q[i].ans += f2[++r];
if(r > q[i].r) v[l - 1].emplace_back(q[i].r + 1, r, i, 1);
while(r > q[i].r)
q[i].ans -= f2[r--];
}
for(re int i = 1, id, l, r, flg; i <= n; ++i)
{
update(a[i]);
for(re const auto& x : v[i])
{
tie(l, r, id, flg) = x;
re ll tmp = 0;
for(re int j = l; j <= r; ++j)
{
if(!flg)
tmp = query(a[j]);
else
tmp = i - query(a[j] + 1);
if(id < 0) q[-id].ans -= tmp;
else q[id].ans += tmp;
}
}
}
for(re int i = 1; i <= m; ++i) q[i].ans += q[i - 1].ans;
for(re int i = 1; i <= m; ++i) Ans[q[i].id] = q[i].ans;
for(re int i = 1; i <= m; ++i) write(Ans[i]), putchar('\n');
}
P5501 [LnOI2019]来者不拒，去者不追
给定一个长度为 \(n\) 的序列 \(a\)。给定 \(m\) 个询问，每次询问一个区间中 \([l,r]\) 中所有数的
Abbi值之和。
Abbi值定义为：若 \(a_i\) 在询问区间 \([l,r]\) 中是第 \(k\) 小，那么它的Abbi值等于 \(k \times a_i\)。\(1 \leq n,m\leq 5\times 10^5,1 \leq a_i \leq 10^5\)，时限 \(1\text{s}\)，空限 \(250\text{MB}\)。
跟上面那题相似。
考虑 \([l,r]\) 转移到 \([l,r+1]\)，即加入一个数的贡献，不难想，即为 \(\sum\limits_{i=l}^{r}[a_i
向上面那题那样搞个值域分块维护一下即可。
细节：上面式子中最后加的那个 \(a_{r+1}\) 并不可以差分（手玩一下可以得知），需要最后加上。
具体参考代码。
\(\text{7.87s / 88.66MB / 3.85KB C++17 O2}\)。
#include
using namespace std;
#define re register
typedef long long ll;
namespace Fread
{
const int SIZE = 1 << 24;
char buf[SIZE], *S, *T;
inline char getchar()
{
if (S == T)
{
T = (S = buf) + fread(buf, 1, SIZE, stdin);
if (S == T)
return '\n';
}
return *S++;
}
}
namespace Fwrite
{
const int SIZE = 1 << 24;
char buf[SIZE], *S = buf, *T = buf + SIZE;
inline void flush()
{
fwrite(buf, 1, S - buf, stdout);
S = buf;
}
inline void putchar(char c)
{
*S++ = c;
if (S == T)
flush();
}
struct NTR
{
~NTR()
{
flush();
}
} ztr;
}
#ifdef ONLINE_JUDGE
#define getchar Fread::getchar
#define putchar Fwrite::putchar
#endif
inline int read()
{
re int x = 0, f = 1;
re char c = getchar();
while (c < '0' || c > '9')
{
if (c == '-')
f = -1;
c = getchar();
}
while (c >= '0' && c <= '9')
{
x = x * 10 + c - '0';
c = getchar();
}
return x * f;
}
inline void write(re ll x)
{
if (x < 0)
{
putchar('-');
x = -x;
}
if (x > 9)
write(x / 10);
putchar(x % 10 + '0');
}
const int _ = 5e5 + 7;
int n, m, S, a[_], bel[_], pre1[_], pree1[_], L[_], R[_], V = 100000;
ll pre[_], pree[_], s[_], F[_], Ans[_];
struct Query
{
int l, r, id;
ll ans;
inline bool operator < (re const Query& tmp)
{
return bel[l] == bel[tmp.l] ? r < tmp.r : l < tmp.l;
}
} q[_];
vector> v[_];
struct tr
{
ll c[_];
void update(re int x, re int val)
{
for(int i = x; i <= V; i += i & -i) c[i] += val;
}
ll query(re int x)
{
ll res = 0;
for(int i = x; i; i -= i & -i) res += c[i];
return res;
}
} t, t1;
void init()
{
memset(pre, 0, sizeof pre);
memset(pree, 0, sizeof pree);
memset(pre1, 0, sizeof pre1);
memset(pree1, 0, sizeof pree1);
}
void update(re int x)
{
for(re int i = bel[x]; i <= bel[V]; ++i) pre[i] += x, pre1[i]++;
for(re int i = x; i <= R[bel[x]]; ++i) pree[i] += x, pree1[i]++;
}
ll query(re int x)
{
return pre[bel[x] - 1] + pree[x];
}
int query1(re int x)
{
return pre1[bel[x] - 1] + pree1[x];
}
signed main()
{
n = read(), m = read();
for(re int i = 1; i <= n; ++i) a[i] = read(), s[i] = s[i - 1] + a[i];
S = 317;
for(re int i = 1; i <= m; ++i)
{
q[i].l = read();
q[i].r = read();
q[i].id = i;
}
for(re int i = 1; i <= V; ++i) bel[i] = (i - 1) / S + 1;
for(re int i = 1; i <= bel[V]; ++i) L[i] = R[i - 1] + 1, R[i] = i * S;
R[bel[V]] = V;
sort(q + 1, q + m + 1);
for(re int i = 1; i <= n; ++i)
{
F[i] = F[i - 1] + 1ll * t1.query(a[i] - 1) * a[i] + t.query(V) - t.query(a[i]);
t.update(a[i], a[i]);
t1.update(a[i], 1);
}
for(re int i = 1, l = 1, r = 0; i <= m; ++i)
{
if(l > q[i].l) v[r].emplace_back(q[i].l, l - 1, i), q[i].ans -= F[l - 1] - F[q[i].l - 1], l = q[i].l;
if(r < q[i].r) v[l - 1].emplace_back(r + 1, q[i].r, -i), q[i].ans += F[q[i].r] - F[r], r = q[i].r;
if(l < q[i].l) v[r].emplace_back(l, q[i].l - 1, -i), q[i].ans += F[q[i].l - 1] - F[l - 1], l = q[i].l;
if(r > q[i].r) v[l - 1].emplace_back(q[i].r + 1, r, i), q[i].ans -= F[r] - F[q[i].r], r = q[i].r;
}
re ll sum = 0;
for(re int i = 1, id, l, r; i <= n; ++i)
{
update(a[i]);
sum += a[i];
for(re const auto& x : v[i])
{
tie(l, r, id) = x;
re ll tmp = 0;
for(re int j = l; j <= r; ++j)
{
tmp = 1ll * query1(a[j] - 1) * a[j] + sum - query(a[j]);
if(id < 0) q[-id].ans -= tmp;
else q[id].ans += tmp;
}
}
}
for(re int i = 1; i <= m; ++i) q[i].ans += q[i - 1].ans;
for(re int i = 1; i <= m; ++i) Ans[q[i].id] = q[i].ans + s[q[i].r] - s[q[i].l - 1];
for(re int i = 1; i <= m; ++i) write(Ans[i]), putchar('\n');
}
P5398 [Ynoi2018] GOSICK
给你一个序列 \(a\)，每次询问给一个区间 \([l,r]\)。
查询 \(l \leq i,j \leq r\) 且 \(a_i\) 是 \(a_j\) 倍数的二元组 \((i,j)\) 的个数。
\(1 \leq n,m,a_i\leq 5\times 10^5\)，时限 \(3\text{s}\)，空限 \(128\text{MB}\)。
sol
「点缀光辉的第十四分块」。
考虑二次离线莫队。
设 \(a_i\) 在区间 \([l,r]\) 的因数个数为 \(f_1(i,[l,r])\)，倍数个数为 \(f_2(i,[l,r])\)。
则右端点向右移动加入一个数的贡献为 \(f_1(r,[l,r])+f_2(r,[l,r])\)。
差分一下即为 \(f_1(r,[1,r])-f_1(r,[1,l-1])+f_2(r,[1,r])-f_2(r,[1,l-1])\)。
\(f_1(r,[1,r])\) 可以在遍历时 \(\mathcal O(\sqrt n)\) 枚举因数，累加所有因数之前的出现次数，定义一个桶即可实现。
\(f_2(r,[1,r])\) 可以在上一个操作枚举因数时对该数的每个因数标记一下，即开一个桶记录该数作为因数的出现次数。
以上两部分可提前预处理，计算前缀和，然后跑一边莫队计算贡献，时间复杂度为 \(\mathcal O(n\sqrt n)\)。
对于 \(f_1(r,[1,l-1])\) 和 \(f_2{r,[1,l-1]}\) 可在上面跑莫队时顺便存下来，进行二次离线，要求 \(\mathcal O(1)\) 查询 \(f_1\) 和 \(f_2\)。
考虑二次离线时的修改，这部分要求是 \(\mathcal O(\sqrt n)\) 级别的。
对于 \(f_1\)，枚举因数，加上贡献即可。
对于 \(f_2\)，考虑根号分治，设阈值 \(S\)：
- 若当前加入的数 \(\geq S\)，暴力跳表，加上贡献。
- 若当前加入的数 \(< S\)，则将这个提出二次离线这部分，后面处理。
二次离线部分时间复杂度为 \(\mathcal O(n \sqrt n)\)。
再考虑刚刚遗留下来的一点东西。
记 \(p[i][j]\) 表示区间 \([1,j]\) 中含有因数 \(i\) 的数的个数，\(c[i][j]\) 表示区间 \([1,j]\) 中 \(i\) 的出现次数。
则区间 \([l,r]\) 中含有因数 \(i\) 的数的个数就是 \(p[i][r] - p[i][l-1]\)。
所以 \([1,z]\) 中的数 \(i\) 作为因数出现在 \([l,r]\) 的总次数为 \(c[i][z]\times (p[i][r] - p[i][l-1])\)。
那么枚举 \(i \in [1,S)\)，\(\mathcal O(n)\) 求出 \(p\) 和 \(c\)（压掉一维），然后 \(\mathcal O(m)\) 计算贡献即可。
所以总时间复杂度为 \(\mathcal O(n \sqrt n)\)，总空间复杂度为 \(\mathcal O(n)\)。
\(\text{32.39s / 75.05MB / 3.92KB C++11 O2}\)。
#include
#include
#include
#include
#include
namespace Fread
{
const int SIZE = 1 << 23;
char buf[SIZE], *S, *T;
inline char getchar()
{
if (S == T)
{
T = (S = buf) + fread(buf, 1, SIZE, stdin);
if (S == T)
return '\n';
}
return *S++;
}
}
namespace Fwrite
{
const int SIZE = 1 << 23;
char buf[SIZE], *S = buf, *T = buf + SIZE;
inline void flush()
{
fwrite(buf, 1, S - buf, stdout);
S = buf;
}
inline void putchar(char c)
{
*S++ = c;
if (S == T)
flush();
}
struct NTR
{
~NTR()
{
flush();
}
} ztr;
}
#ifdef ONLINE_JUDGE
#define getchar Fread::getchar
#define putchar Fwrite::putchar
#endif
typedef long long ll;
inline int read()
{
int x = 0, f = 1;
char c = getchar();
while(c < '0' || c > '9')
{
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9')
{
x = x * 10 + c - '0';
c = getchar();
}
return x * f;
}
inline void write(ll x)
{
if(x < 0)
{
putchar('-');
x = -x;
}
if(x > 9)
write(x / 10);
putchar(x % 10 + '0');
}
const int _ = 5e5 + 7, S = 100;
int n, m, k, a[_], bel[_], siz, mx, cnt[_], flg[_], pre[_];
ll f[_], Ans[_];
struct Query
{
int l, r, id;
ll ans;
inline bool operator < (const Query &t) const
{
return bel[l] == bel[t.l] ? (bel[l] & 1 ? r < t.r : r > t.r) : bel[l] < bel[t.l];
}
} q[_];
struct Node
{
int l, r, id, x;
bool operator < (const Node &t) const
{
return x < t.x;
}
} t[_ << 1];
std::vector fac[_];
signed main()
{
n = read(), m = read();
siz = sqrt(n);
for(int i = 1; i <= n; ++i)
{
a[i] = read();
bel[i] = (i - 1) / siz + 1;
mx = std::max(mx, a[i]);
if(fac[a[i]].empty())
{
for(int j = 1; j * j <= a[i]; ++j)
if(a[i] % j == 0)
{
f[i] += cnt[j];
flg[j]++;
if(j * j != a[i])
{
f[i] += cnt[a[i] / j];
flg[a[i] / j]++;
}
fac[a[i]].emplace_back(j);
}
}
else
{
for(int x : fac[a[i]])
{
f[i] += cnt[x];
flg[x]++;
if(x * x != a[i])
{
f[i] += cnt[a[i] / x];
flg[a[i] / x]++;
}
}
}
f[i] += f[i - 1] + flg[a[i]];
cnt[a[i]]++;
}
for(int i = 1; i <= m; ++i)
q[i] = {read(), read(), i, 0};
std::sort(q + 1, q + m + 1);
for(int i = 1, l = 1, r = 0; i <= m; ++i)
{
if(r < q[i].r) t[++k] = {r + 1, q[i].r, -i, l - 1}, q[i].ans += f[q[i].r] - f[r], r = q[i].r;
if(l > q[i].l) t[++k] = {q[i].l, l - 1, i, r}, q[i].ans -= f[l - 1] - f[q[i].l - 1], l = q[i].l;
if(r > q[i].r) t[++k] = {q[i].r + 1, r, i, l - 1}, q[i].ans -= f[r] - f[q[i].r], r = q[i].r;
if(l < q[i].l) t[++k] = {l, q[i].l - 1, -i, r}, q[i].ans += f[q[i].l - 1] - f[l - 1], l = q[i].l;
}
std::sort(t + 1, t + k + 1);
memset(f, 0, sizeof f);
for(int i = 1, x = 0; i <= k; ++i)
{
while(x < t[i].x)
{
x++;
for(int v : fac[a[x]])
{
f[v]++;
if(v * v != a[x])
f[a[x] / v]++;
}
if(a[x] > S)
for(int j = 1; j * a[x] <= mx; ++j)
f[j * a[x]]++;
}
for(int k = t[i].l; k <= t[i].r; ++k)
if(t[i].id < 0)
q[-t[i].id].ans -= f[a[k]];
else
q[t[i].id].ans += f[a[k]];
}
for(int i = 1; i <= S; ++i)
{
cnt[0] = pre[0] = 0;
for(int j = 1; j <= n; ++j)
{
cnt[j] = cnt[j - 1] + (a[j] == i);
pre[j] = pre[j - 1] + (a[j] % i == 0);
}
for(int j = 1; j <= k; ++j)
if(t[j].id < 0)
q[-t[j].id].ans -= (ll)cnt[t[j].x] * (ll)(pre[t[j].r] - pre[t[j].l - 1]);
else
q[t[j].id].ans += (ll)cnt[t[j].x] * (ll)(pre[t[j].r] - pre[t[j].l - 1]);
}
for(int i = 1; i <= m; ++i)
{
q[i].ans += q[i - 1].ans;
Ans[q[i].id] = q[i].ans;
}
for(int i = 1; i <= m; ++i)
write(Ans[i]), putchar('\n');
}