卡常带师

大力分块3

背景

上次做毒瘤分块还是上次：大力分块2

这次就是这次了（已经好久没做）

要问为什么隔了这么远（第六分块过了就是第十四），主要矛盾是我太弱了不会

第十四分块

「点缀光辉的第十四分块」

给定一个长度为 $n \le 5 \times 10^5$ 的序列 $a_i \le 5 \times 10^5$ ， $m \le 5 \times 10^5$ 次询问，每次给定 $l, r \in [1, n]$ ，询问满足 $l \le i < j \le r$ 且 $a_i$ 是 $a_j$ 的倍数的 $(i, j)$ 有多少对

前置知识：二次离线

不懂的可以康康这个，或者自己去找找网上的资料

思路

如果你会了二次离线，那么这题的思路就还算简单了

考虑数 $x$ 对区间 $[l, r]$ 的贡献（记它为 $f(x, [l ,r])$ ），明显就是 $[l, r]$ 中 $x$ 的倍数的个数 + $x$ 的约数的个数

考虑莫队，直接维护指针移动时间复杂度过高，我们用二次离线，那么我们要解决的就是 $f(x, [1, x - 1])$ 和 $f([L, R], [1, k])$

先考虑贡献中的第一部分，即“ $[l, r]$ 中 $x$ 的倍数的个数”，我们开个桶 $b[t]$ ，表示“区间内 $t$ 的倍数的个数”，每次插入一个数时就枚举其因数跟新 $b$ ，由于一个数的因数个数小于 $\sqrt{n}$ ，所以可做

再考虑第二部分，即“ $[l, r]$ 中 $x$ 的约数的个数”，这里我们就不能用和第一部分相同的办法了，因为当 $x$ 比较小的时候， $n$ 以内的 $x$ 的倍数可能很多，枚举倍数时间不允许

但这里的“不允许”是对于计算 $f([L, R], [1, k])$ 来说的，因为它要求插入时间最大 $O(\sqrt{n})$ ，对于 $x \in [L, R]$ 询问 $f(x, [1, k])$ 是 $O(1)$ （或者 $[L, R]$ 整体询问 $O(\sqrt{n})$ ）；而 $f(x, [1, x - 1])$ 不会有这个问题，因为我们可以直接不枚举倍数，去枚举 $x$ 的约数，用 $O(\sqrt{n})$ 的询问解决

对 $f([L, R], [1, k])$ ，考虑平衡规划，对于 $x \ge V$ 的情况，我们直接枚举倍数，时间为 $\frac{n}{V}$

而对于 $x \le V$ 的部分，维护 $ct1[i, j]$ 表示“前 $i$ 个数中有多少个等于 $j$ ”，再维护 $ct2[i, j]$ 表示“前 $i$ 个数中有多少个含约数 $j$ ”（上面的 $j$ 都 $\le V$ ，上面定义就用了前缀和的形式，是为了方便使用）

于是， $f([L, R], [1, k])$ 就是 $\sum _{j = 1}^V ct1[k, j] \times (ct2[R, j] - ct2[L - 1, j])$ ，不难发现 $[L, R]$ 的整体复杂度为 $O(V)$ ；取 $V = \sqrt{n}$ 时间最优

另外，由于 lxl 卡空间，我们开不了二维数组，发现 $ct1/2[i, j]$ 我们的式子只用同一个 $j$ ，所以只记 $ct1[i], ct2[i]$ ，把 $j$ 放到最外层枚举，计算完 $ct1, ct2$ 后立刻去跟新贡献，然后再去存下一个 $j$

卡常

lxl 是不会让你轻松过的：

快读快输、 inline
把每个数的约数预处理了（只存 $\le \sqrt{n}$ 的）
卡块长，实测 $V = 50 / 30$ 时比较优秀， $B$ 对本题影响不大，直接取 $\sqrt{n}$ 即可过，但仍然实测 $B = 700 \sim 800$ 时比较优秀
这个很重要！我们发现如果我们还是直接给 $1 \sim n$ 每个数开一个 vector 来存二次离线的标记的话，理论时间是正确的，但在平衡规划处，由于我们是枚举 $j \in [1, V]$ ，每次计算完 $ct1, ct2$ 后就要马上枚举每个标记去跟新，而 STL 慢的和 shit 一样（主要是因为要枚举所以的 $i \in [1, n]$ 但有的 $i$ 根本没有标记，枚举它是多余的；再就是空间不连续，访问时慢的让我想死），所以要手打记录标记的数组（记得开二倍）
向 lxl 和 luogu 祈祷（折寿）吧

代码

ps ：不知道为啥有几次提交会报一个什么“致命错误”，但再交就又过了

#include <vector>
#include <iostream>
#include <algorithm>
#include <cmath>
#define STC static
#define IL inline
namespace FastIO
{
    const int L = (1 << 20) + 5;
    char *E, *S, buf[L], out[L];
    int l = 0;
    #define gh() (E == S ? E = (S = buf) + fread(buf, 1, L, stdin), (E == S ? EOF : *S++) : *S++)
    template<class T>
    IL void read(T &x)
    {
        char ch = gh(), t = 0;
        for ( ; ch < '0' || ch > '9'; ch = gh()) t |= ch == '-';
        for (x = 0; ch >= '0' && ch <= '9'; ch = gh()) x = x * 10 + (ch ^ 48);
        if (t) x = -x;
    }
    IL void flus(){ fwrite(out, 1, l, stdout), l = 0; }
    IL void check(){ if (l >= L - 5) flus(); }
    IL void putc(char x){ out[l++] = x, check(); }
    template<class T>
    IL void write(T x)
    {
        if (x < 0) putc('-'), x = -x;
        if (x > 9) write(x / 10);
        out[l++] = x % 10 + 48, check();
    }
}
using FastIO::read;
using FastIO::flus;
using FastIO::putc;
using FastIO::write;
using LL = long long;
const int N = 5e5 + 5, V = 50;
int n, m, a[N], tp;
LL f[N], ans[N];
struct Ques{ int l, r, id; LL ans; } q[N];
struct Tag{ int l, r, id, pos; } tag[N << 1];
std::vector<int> fac[N];
IL void prev()
{
    STC int cnt[N], b[N], bid[N];
	int B = sqrt(n);
    for (int i = 1; i <= n; f[i] += f[i - 1] + b[a[i]], ++cnt[a[i]], ++i)
        if (fac[a[i]].empty())
        {
            for (int j = 1; j * j <= a[i]; ++j)
                if (a[i] % j == 0)
                {
                    fac[a[i]].push_back(j);
                    ++b[j], f[i] += cnt[j];
                    if (j * j != a[i]) ++b[a[i] / j], f[i] += cnt[a[i] / j];
                }
        }
        else
            for (int j : fac[a[i]])
            {
                ++b[j], f[i] += cnt[j];
                if (j * j != a[i]) ++b[a[i] / j], f[i] += cnt[a[i] / j];
            }
    for (int i = 1; i <= n; ++i) bid[i] = (i - 1) / B + 1;
    std::sort(q + 1, q + m + 1, [&](Ques a, Ques b){ return (bid[a.l] ^ bid[b.l]) ? a.l < b.l : a.r < b.r; });
}
IL void add_tag() //顺便把预处理的值加了
{
    for (int i = 1, il = 1, ir = 0; i <= m; ++i)
    {
        if (il > q[i].l) q[i].ans -= f[il - 1] - f[q[i].l - 1], tag[++tp] = {q[i].l, il - 1, i, ir};
        else if (il < q[i].l) q[i].ans += f[q[i].l - 1] - f[il - 1], tag[++tp] = {il, q[i].l - 1, -i, ir};
        il = q[i].l;
        if (ir < q[i].r) q[i].ans += f[q[i].r] - f[ir], tag[++tp] = {ir + 1, q[i].r, -i, il - 1};
        else  if (ir > q[i].r) q[i].ans -= f[ir] - f[q[i].r], tag[++tp] = {q[i].r + 1, ir, i, il - 1};
        ir = q[i].r;
    }
	std::sort(tag + 1, tag + tp + 1, [&](Tag a, Tag b){ return a.pos < b.pos; });
}
IL void offline()
{
    STC int b[N], ct1[N], ct2[N];
    for (int i = 1, p = 0; i <= tp; ++i)
    {
		while (p < tag[i].pos)
		{
			++p;
			for (int x : fac[a[p]]) ++b[x], b[a[p] / x] += (x * x != a[p]);
			if (a[p] > V) for (int j = 1; j * a[p] < N; ++j) ++b[j * a[p]];
		}
		for (int j = tag[i].l, k = tag[i].id < 0 ? -1 : 1; j <= tag[i].r; ++j) q[tag[i].id * k].ans += b[a[j]] * k;
    }
    for (int j = 1; j <= V; ++j) //平衡规划
    {
        ct1[0] = ct2[0] = 0;
        for (int i = 1; i <= n; ++i) ct1[i] = ct1[i - 1] + (a[i] == j), ct2[i] = ct2[i - 1] + (a[i] % j == 0);
        for (int i = 1; i <= tp; ++i)
		{
			int k = tag[i].id < 0 ? -1 : 1;
			q[tag[i].id * k].ans += (LL(ct2[tag[i].r] - ct2[tag[i].l - 1]) * ct1[tag[i].pos]) * k;
		}
    }
}
int main()
{
	read(n), read(m);
    for (int i = 1; i <= n; ++i) read(a[i]);
    for (int i = 1; i <= m; ++i) read(q[i].l), read(q[i].r), q[i].id = i;
    prev(), add_tag(), offline();
    for (int i = 1; i <= m; ++i) q[i].ans += q[i - 1].ans;
    for (int i = 1; i <= m; ++i) ans[q[i].id] = q[i].ans;
   	for (int i = 1; i <= m; ++i) write(ans[i]), putc('\n');
    return flus(), 0;
}

废话

强烈推荐去看 GOSICK ，对它每集很文艺的标题和男主“打完这场仗……”的 flag 印象很深

待续

但后面都好难啊……