通用算法

基础算法

常作为其它算法的基础。

快速乘 & 快速幂

快速乘可避免模数大于 $int$ 取值范围时溢出，可将快速幂中乘法替换为快速乘版本以避免乘法溢出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
i64 qmul(i64 x, i64 y, i64 m) {
    i64 z = (f80) x / m * y + 0.5L;
    u64 c = (u64) x * y - (u64) z * m;
    return c < m ? (i64) c : (i64) (c + m);
}

i64 qpow(i64 a, i64 n, i64 m) {
    i64 res = 1;
    while (n) {
        if (n & 1) res = res * a % m;
        a = a * a % m;
        n >>= 1;
    }
    return res;
}

Barrett 模乘

Barrett 模乘是一种通过预计算除数的倒数来优化模运算的高效算法，用乘法和移位代替除法，在模数编译期未知的情况下可以优化取模（如 Pollard-Rho 算法）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
struct Barrett {  
    i64 d;  
    i128 b;  
  
    explicit Barrett(i64 d) : d(d), b(((i128) 1 << 64) / d) {  
    }  
  
    friend i64 operator %(i64 a, const Barrett &m) {  
        i64 w = (m.b * a) >> 64;  
        w = a - w * m.d;  
        return w >= m.d ? w - m.d : w;
    }  
  
    friend i64 operator /(i64 a, const Barrett &d) {  
        i64 w = (d.b * a) >> 64;  
        return a - w * d.d >= d.d ? w + 1 : w;  
    }  
};

基姆拉尔森计算公式

以 1970 年 1 月 1 日为星期四为基准，累加日期计算 y 年 m 月 d 日是星期几。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
const int ds[] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};  
  
bool is_leap(int y) {  
    return y % 400 == 0 || (y % 4 == 0 && y % 100 != 0);  
}  
  
int get_days(int y, int m) {  
    return ds[m - 1] + (is_leap(y) && m == 2);  
}  
  
int get_week(int y, int m, int d) {  
    int res = 2;  
    for (int i = 1970; i < y; i++) res += 365 + is_leap(i);  
    for (int i = 1; i < m; i++) res += get_days(y, i);  
    res += d;  
    return res % 7 + 1;  
}

蔡勒公式

基准相同，可以快速计算任意年份，返回 0 代表星期日。

1
2
3
4
5
int get_week(int y, int m, int d)  
{  
    if (m == 1 || m == 2) m += 12, y--;  
    return (d + 2 * m + 3 * (m + 1) / 5 + y + y / 4 - y / 100 + y / 400 + 1) % 7;  
}

三分算法

整数范围凹函数三分算法，实现了对函数平台区域的处理，若平均平台长度为 $k$ ，则期望复杂度约为 $O(k\log{n})$ 。

1
2
3
4
5
6
7
8
9
10
i64 l = 0, r = 1e18, al, ar;
while (l < r) {
    i64 ml = (l + r) / 2, mr = ml + 1;
    al = f(ml), ar = f(mr);
    while (al == ar && ml > l) al = f(--ml);

    if (al >= ar) l = mr;
    else r = ml;
}
cout << min(al, ar) << endl;

排序算法

排序算法是将数据排列的方法，在基础排序算法的基础上上可以扩展出更多功能。

快速排序

基于随机选取基数的三路快速排序，是不稳定排序，可以在此基础上修改出线性找第 $k$ 大的数算法。

1
2
3
4
5
6
7
8
9
10
11
12
auto qsort = [&](auto &&self, int l, int r) {
    if (r - l <= 1) return;
    auto pivot = a[l + rnd() % (r - l)];
    int i = l, j = l, k = r;
    while (i < k) {
        if (a[i] < pivot) swap(a[i++], a[j++]);
        else if (a[i] > pivot) swap(a[i], a[--k]);
        else i++;
    }
    self(self, l, j);
    self(self, k, r);
};

归并排序

基于分治思想将数组分段排序后合并，是稳定排序，可以在此基础上修改用于解决偏序问题其中一维。

1
2
3
4
5
6
7
8
9
10
11
12
13
auto msort = [&](auto self, int l, int r) {
    if (r - l <= 1) return;
    int m = l + r >> 1;
    self(self, l, m), self(self, m, r);
    int i = l, j = m, k = l;
    while (i < m && j < r) {
        if (a[i] <= a[j]) b[k++] = a[i++];
        else b[k++] = a[j++];
    }
    while (i < m) b[k++] = a[i++];
    while (j < r) b[k++] = a[j++];
    for (i = l; i < r; ++i) a[i] = b[i];
};

搜索算法

搜索，也就是对状态空间进行枚举，通过穷尽所有的可能来找到最优解，或者统计合法解的个数。

精确覆盖问题要求在给定集合中选取若干互不相交的子集，使得目标集合的每个元素恰好被覆盖一次。

Dancing Links X 算法通过高效回溯和双向链表优化搜索，常用于解决数独、 N 皇后、 Pentomino 拼图等组合优化问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
struct DLX {
    struct node {
        int l = 0, r = 0, u = 0, d = 0, row = -1, col = -1;
    };

    vector<node> adj;
    vector<int> head, sz, ans;

    explicit DLX(int r, int c) : adj(c + 1), head(r + 1, -1), sz(c + 1) {
        for (int i = 0; i <= c; ++i) {
            adj[i].l = i - 1, adj[i].r = i + 1;
            adj[i].u = adj[i].d = adj[i].col = i;
        }
        adj[0].l = c, adj[c].r = 0;
    }

    void insert(int r, int c) {
        int id = (int) adj.size();
        adj.emplace_back(0, 0, adj[c].u, c, r, c);
        adj[c].u = adj[adj[c].u].d = id;
        if (head[r] == -1) {
            head[r] = adj[id].l = adj[id].r = id;
        } else {
            int first = head[r];
            int last = adj[first].l;
            adj[id].l = last, adj[id].r = first;
            adj[last].r = adj[first].l = id;
        }
        sz[c]++;
    }

    void remove(int c) {
        adj[adj[c].r].l = adj[c].l;
        adj[adj[c].l].r = adj[c].r;
        for (int i = adj[c].d; i != c; i = adj[i].d) {
            for (int j = adj[i].r; j != i; j = adj[j].r) {
                adj[adj[j].d].u = adj[j].u;
                adj[adj[j].u].d = adj[j].d;
                sz[adj[j].col]--;
            }
        }
    }

    void restore(int c) {
        for (int i = adj[c].u; i != c; i = adj[i].u) {
            for (int j = adj[i].l; j != i; j = adj[j].l) {
                adj[adj[j].d].u = adj[adj[j].u].d = j;
                sz[adj[j].col]++;
            }
        }
        adj[adj[c].r].l = adj[adj[c].l].r = c;
    }

    bool dance() {
        if (adj[0].r == 0) return true;
        int c = adj[0].r;
        for (int i = adj[c].r; i != 0; i = adj[i].r) {
            if (sz[i] < sz[c]) c = i;
        }
        remove(c);
        for (int i = adj[c].d; i != c; i = adj[i].d) {
            ans.push_back(adj[i].row);
            for (int j = adj[i].r; j != i; j = adj[j].r) remove(adj[j].col);
            if (dance()) return true;
            for (int j = adj[i].l; j != i; j = adj[j].l) restore(adj[j].col);
            ans.pop_back();
        }
        restore(c);
        return false;
    }
};

数独问题

使用 Dancing links X 算法高效解决数独问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
array<array<int, 9>, 9> ma{};
auto get = [&](int x, int y, int k)-> array<int, 4> {
    int box = x / 3 * 3 + y / 3;
    return {
        x * 9 + y + 1,
        81 + x * 9 + k + 1,
        162 + y * 9 + k + 1,
        243 + box * 9 + k + 1
    };
};

int id = 0;
DLX solver(730, 324);
vector<tuple<int, int, int> > rows;
for (int x = 0; x < 9; ++x) {
    for (int y = 0; y < 9; ++y) {
        if (ma[x][y] != 0) {
            int k = ma[x][y] - 1;
            for (int c: get(x, y, k)) solver.insert(id, c);
            rows.emplace_back(x, y, k);
            id++;
        } else {
            for (int k = 0; k < 9; ++k) {
                for (int c: get(x, y, k)) solver.insert(id, c);
                rows.emplace_back(x, y, k);
                id++;
            }
        }
    }
}

solver.dance();
for (int rid: solver.ans) {
    auto [x, y, k] = rows[rid];
    ma[x][y] = k + 1;
}

动态规划算法

具有最优子结构，无后效性和子问题重叠的问题可以使用动态规划解决。

完全背包 DP

定义价值重量比为价值与重量的比值，则第 $i$ 种物品的价值重量比为 $\frac{v_i}{w_i}$ 。

设第 $s$ 种物品为价值重量比最大的那些物品之中重量最小的那种物品。

设使承重量为 $W$ 的背包所能获得最大价值的方案中，有 $a$ 件非第 $s$ 种物品，有 $b$ 件第 $s$ 种物品。

于是转化为有 $x$ 件非第 $s$ 种物品， $y$ 件第 $s$ 种物品，且在这 $x$ 件非第 $s$ 种物品中，不存在若干件物品的重量和为 $w_s$ 的倍数。

由鸽笼原理得：$x$ < $w_s$ ，故这 $x$ 件物品的重量和最大为$(w_s−1)max(w_i),i≠s$ 。

$$ans = max(dp[w] +\lfloor(W-w)\div{w_s}\rfloor\times{v_s}),1\leq{w}\leq (w_s-1)max(w_i),i\neq{s}$$

执行这样的 dp ，可以在 $O(nu^2)$ 的时间复杂度解决完全背包问题，其中 $u$ 为最大的物品重量。

以下代码提供了简洁的实现，并使用数论方法将时间复杂度优化到 $O(nu\log{u})$ 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
vector<int> id(n);  
iota(id.begin(), id.end(), 0);  
ranges::sort(id, [&](int x, int y) {  
    return (i64) v[x] * w[y] > (i64) v[y] * w[x];  
});  
  
vector<i64> dp(min(W, u * u) + 1);  
for (int i = 1; i <= min(W, u * u); ++i) {  
    for (int j = 0; j < min((3 * u * u + i - 1) / i, n); ++j) {  
        if (w[id[j]] <= i) dp[i] = max(dp[i], dp[i - w[id[j]]] + v[id[j]]);  
    }  
}  
i64 m = (max(0, W - u * u) + w[id[0]] - 1) / w[id[0]];  
i64 ans = dp[W - m * w[id[0]]] + m * v[id[0]];

混合背包 DP

单调队列优化的背包 DP 可以以 $O(nW)$ 的时间复杂度解决混合背包问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
vector<int> dp(W + 1);
for (int i = 0; i < n; i++) {
    for (int j = 0; j < w[i]; j++) {
        deque<info> deq;
        for (int k = 0; k * w[i] + j <= W; k++) {
            int val = dp[k * w[i] + j] - k * v[i];
            while (!deq.empty() && val > deq.back().val) deq.pop_back();
            deq.emplace_back(k, val);
            if (deq.front().k < k - d[i]) deq.pop_front();
            dp[k * w[i] + j] = deq.front().val + k * v[i];
        }
    }
}

状压 DP

状压 DP 通过将状态压缩为整数来达到优化转移的目的。

旅行商问题

旅行商问题求经过每个点的一次或多次的最短回路或通路，是组合优化中的一个 NPH 问题。

$dp[i][j]$ 表示经过状态 $i$ 所表示的点，到达 $j$ 点的最短通路，经过恰当的初始化和后处理可以解决各类旅行商问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
constexpr int inf = 1e9;
array<int, 20> val{};
val.fill(inf);
vector<array<int, 20> > dp(1 << n, val);
for (int i = 0; i < n; ++i) dp[1 << i][i] = 0;
for (int i = 0; i < 1 << n; ++i) {
    for (int j = 0; j < n; ++j) {
        if (dp[i][j] == inf) continue;
        for (int k = 0; k < n; ++k) {
            if (i & 1 << k) continue;
            dp[i + (1 << k)][k] = min(dp[i + (1 << k)][k], dp[i][j] + maxd[j][k]);
        }
    }
}

数位 DP

数位 DP 主要用于解决 “在区间范围内，满足某种约束的数字的数量、总和、平方” 这一类问题。

状态（形参）设置

以下为记忆化搜索函数常设定的形参。

  • pos: int 型变量，表示当前枚举的位置，一般从高到低
  • limit: bool 型变量，表示枚举的第 pos 位是否受到限制
    • 为 true 表示取的数不能大于 a[pos]，而只有在 [pos + 1, len] 的位置该值才为 ture
    • 否则表示当前位没有限制，可以取到 [0, R - 1] ，因为 R 进制的数中最大能取到的就是 R - 1
  • last: int 型变量，表示上一位（第 pos + 1 位）填写的值
    • 往往用于约束了相邻数位之间的关系的题目，可以存 -1 以代替 lead0 状态
  • lead0: int 型变量，表示是否有前导零，即在 [pos + 1, len] 这些位置是不是都是前导零
    • 基于常识，我们往往默认一个数没有前导零，也就是最高位不能为 0 ，即不会写为 000123 而是 123
    • 只有没有前导零的时候，才能计算 0 的贡献
    • 以下常见情况需要考虑处理前导零
      • 统计 0 的出现次数
      • 相邻数字的差值
      • 以最高位为起点确定的位数
  • sum : int 型变量，表示当前 [pos + 1, len] 的数位和或数字出现个数
  • r : int 型变量，表示整个数前缀取模某个数 p 的余数
    • 该参数一般会用在：约束中出现了能被 p 整除
    • 当然也可以拓展为数位和取模的结果
  • st : int 型变量，用于状态压缩
    • 对一个集合的数在数位上的出现次数的奇偶性有要求时，其二进制形式就可以表示每个数出现的奇偶性
    • 通过四进制可以同时保存数字是否出现以及奇偶信息，且奇偶互换为对应位取反

数位 k 的出现次数

下面展示了一个查找 [0, x] 范围内不计前导 0 的数字中数位为 k 的数位个数的记忆化搜索实现。

limit 和 lead0 参数为 true 所确定的子问题不会出现重复且至多出现 a.size() 次，因此无需记忆化。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
auto get = [&](int x, int k) {
    vector<int> a{0};
    while (x) a.push_back(x % 10), x /= 10;
    vector mem(a.size(), vector<int>(a.size(), -1));
    auto dfs = [&](auto &&self, int pos, bool limit, bool lead0, int sum) -> int {
        if (!pos) return sum;
        if (!limit && !lead0 && ~mem[pos][sum]) return mem[pos][sum];
        int res = 0;
        int up = limit ? a[pos] : 9;
        for (int i = 0; i <= up; i++) {
            int c0 = lead0 && i == 0;
            res += self(self, pos - 1, limit && i == up, c0, c0 ? 0 : sum + (i == k));
        }
        if (!limit && !lead0) mem[pos][sum] = res;
        return res;
    };
    return dfs(dfs, a.size() - 1, true, true, 0);
};

离线算法

算法在求解问题已具有与该问题相关的完全信息。

CDQ 分治

类似归并排序的思想，先按第一维属性划分为前一半和后一半，合并时计算前一半区间对后一半区间的影响。

三维偏序

一维排序，二维 CDQ 分治 ，三维树状数组，包含去重代码。

第一维相等时，后续维可以按相反弱序关系排序，以处理第一维非严格偏序问题。

当三维均不存在严格偏序关系时，答案贡献关系成环，不存在一种正确的更新顺序，此时需要先去重。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int s = 0, c = 0;
for (int f = 0; f < n; c += a[f++].c) {
    if (a[s].x == a[f].x && a[s].y == a[f].y && a[s].z == a[f].z) continue;
    a[s].c = c, a[s].a = c - 1;
    a[++s] = a[f], c = 0;
}
a[s].c = c, a[s].a = c - 1;
a.resize(++s);

Fenwick<int> bit(k + 1);
auto cdq = [&](auto &&self, int l, int r) -> void {
    if (r - l <= 1) return;
    int m = l + r >> 1;
    self(self, l, m), self(self, m, r);
    int i = l, j = m;
    while (j < r) {
        while (i < m && a[i].y <= a[j].y) bit.add(a[i].z, a[i].c), i++;
        a[j].a += bit.sum(a[j].z), j++;
    }
    for (j = l; j < i; j++) bit.add(a[j].z, -a[j].c);
    inplace_merge(a.begin() + l, a.begin() + m, a.begin() + r, cmpy);
};
cdq(cdq, 0, s);

整体二分

整体二分是一种离线分治算法，通过将多个查询或操作批量处理并递归地将问题划分为子问题，结合二分思想高效解决带有批量询问和更新的复杂问题。

带修区间第 k 小

下列代码使用整体二分的方法，通过将修改和查询抽象成操作序列，解决了了带修区间第 $k$ 小问题，时间复杂度 $O(n\log^2{n})$。

  • Q l r k 表示查询下标在区间 $[l,r]$ 中的第 $k$ 小的数
  • C x y 表示将 $a_x$ 改为 $y$。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
struct info {
    char op;
    int l, r, k, x, y, v, i;
};

vector<int> ans(m);
Fenwick<int> f(n + 1);
auto qsort = [&](auto &&self, int l, int r, vector<info> &cq) {
    if (r - l == 1) {
        for (auto &i: cq) {
            if (i.op == 'Q') ans[i.i] = l;
        }
        return;
    }
    int mid = (l + r) / 2;
    vector<info> q1, q2;
    for (auto i: cq) {
        if (i.op == 'Q') {
            int cnt = f.sum(i.r) - f.sum(i.l - 1);
            if (cnt >= i.k) q1.push_back(i);
            else q2.push_back(i), q2.back().k -= cnt;
        } else {
            if (i.y < mid) f.add(i.x, i.v), q1.push_back(i);
            else q2.push_back(i);
        }
    }
    for (auto i: cq) {
        if (i.op == 'C' && i.y < mid) f.add(i.x, -i.v);
    }
    if (!q1.empty()) self(self, l, mid, q1);
    if (!q2.empty()) self(self, mid, r, q2);
};

静态序列优化

维护一个指针 $pos$ 追踪每轮划分的 $mid$，对于绝大多数可以用整体二分解决并且不带修改的问题，都可以应用此种优化以大幅降低数据结构的使用次数，注意不需要对询问做出修改。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
struct info {  
    int l, r, k, i;  
};  
  
struct num {  
    int v, i;  
};

int pos = 0;  
vector<int> ans(m);  
Fenwick<int> f(n + 1);  
ranges::sort(a, [](auto x, auto y) { return x.v < y.v; });  
auto qsort = [&](auto &&self, int l, int r, const vector<info> &cq) {  
    if (r - l == 1) {  
        for (auto &i: cq) ans[i.i] = l;  
        return;  
    }  
    int mid = l + (r - l >> 1);  
    while (pos < n && a[pos].v < mid) f.add(a[pos++].i, 1);  
    while (pos > 0 && a[pos - 1].v >= mid) f.add(a[--pos].i, -1);  
    vector<info> q1, q2;  
    for (auto i: cq) {  
        int cnt = f.sum(i.r) - f.sum(i.l - 1);  
        if (cnt >= i.k) q1.push_back(i);  
        else q2.push_back(i);  
    }  
    if (!q1.empty()) self(self, l, mid, q1);  
    if (!q2.empty()) self(self, mid, r, q2);  
};

莫队算法

莫队算法是分块思想在查询上的应用，可以解决一类离线区间询问问题。

莫队算法的最优块长与更新块操作的效率有关，属于玄学，因此复杂度分析仅供图一乐。

普通莫队算法

若扩展到相邻区间操作复杂度 $O(a)$ ，转移完毕后计算区间答案复杂度 $O(b)$，块长 s 为 $\frac{n}{\sqrt{q}}$ ，则有最优总复杂度 $O(a*n\sqrt{q} + b * q)$ 。

常用莫队维护权值块状数组，此时总复杂度 $O(n\sqrt{q})$ 。

1
2
3
4
5
6
7
8
9
10
11
12
13
int len = (int) (n / sqrt(m)); 
ranges::sort(qs, [&](auto x, auto y) {
    if (x.l / len != y.l / len) return x.l < y.l;
    return x.l / len & 1 ? x.r > y.r : x.r < y.r;
});

for (auto &q: qs) {
    while (l > q.l) move(--l, 1);
    while (r < q.r) move(r++, 1);
    while (l < q.l) move(l++, -1);
    while (r > q.r) move(--r, -1);
    q.ans = query();
}

回滚莫队

回滚莫队仅在端点扩展时添加元素，通过回滚（撤销）操作避免删除，最坏时间复杂度与普通莫队算法相同，但是回滚莫队缺乏优化，复杂度更紧。

下列代码使用回滚莫队的方法，解决了区间带权众数问题，时间复杂度 $O(n\sqrt{q})$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
int len = (int) (n / sqrt(m));  
ranges::sort(qs, [&](auto x, auto y) {  
    if (x.l / len != y.l / len) return x.l < y.l;  
    return x.r < y.r; // 注意不能使用奇偶优化
});  
  
i64 ans = 0;  
vector<int> cnt(cv.size()), cnt1(cv.size());  
auto move = [&](int x) {  
    ans = max(ans, (i64) ++cnt[b[x]] * a[x]);  
};  
  
int l = -1e9, r = 0;  
for (auto &q: qs) {  
    if (q.l / len == q.r / len) { // 暴力回答问题
        for (int i = q.l; i < q.r; i++) cnt1[b[i]] = 0;  
        for (int i = q.l; i < q.r; i++) {  
            q.ans = max(q.ans, (i64) ++cnt1[b[i]] * a[i]);  
        }  
        continue;  
    }  
    if (q.l / len != l / len - 1) { // 初始化左右端点
        ans = 0;  
        cnt.assign(cv.size(), 0);  
        l = r = (q.l / len + 1) * len;  
    }  
    while (r < q.r) move(r++); // 扩展右端点
    i64 tmp = ans;  // 记录信息
    while (l > q.l) move(--l); // 扩展左端点
    while (l < (q.l / len + 1) * len) cnt[b[l++]]--;  
    q.ans = ans, ans = tmp; // 回滚信息
}

带修改莫队

普通莫队是不能带修改的，但可以强行加上一维时间维 t 表示经历的修改次数，变成三维莫队问题。

即把询问 $[l, r]$ 变成 $[l, r, t]$，那么我们的坐标也可以在时间维上移动。

若三个维度数量级分别为 $x$, $y$, $z$，查询次数为 $q$ ，块长为 $s$ ，则复杂度为 $O(\frac{xyz}{s^{2}}+qs)$，求导得块长 $s$ 取 $\dfrac{x^{1/3}y^{1/3}z^{1/3}}{q^{1/3}}$ 时有最优复杂度 $O(x^{1/3}y^{1/3}z^{1/3}q^{2/3})$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
const int len = (int) pow(n, 0.67);
ranges::sort(qs, [&](auto &x, auto &y) {
    if (x.l / len != y.l / len) return x.l < y.l;
    if (x.r / len != y.r / len) return x.l / len & 1 ? x.r > y.r : x.r < y.r;
    return x.r / len & 1 ? x.t < y.t : x.t > y.t;
});

auto movet = [&](int i, int val) {
    auto [x, u, v] = ms[i];
    if (val == -1) swap(u, v);
    a[x] = v;
    if (x < l || x >= r) return;
    cnt[u]--, b[bk[u]]--;
    cnt[v]++, b[bk[v]]++;
};

for (auto &q: qs) {
    while (l > q.l) movelr(--l, 1);
    while (r < q.r) movelr(r++, 1);
    while (l < q.l) movelr(l++, -1);
    while (r > q.r) movelr(--r, -1);
    while (t < q.t) movet(++t, 1);
    while (t > q.t) movet(t--, -1);
    q.ans = query();
}

莫队二次离线

通过将莫队算法中的指针移动产生的询问二次离线处理，利用预处理信息优化时间复杂度。

适用于指针移动代价高的统计问题，先按莫队排序处理查询并记录指针移动的贡献，再离线批量计算这些贡献，关键点包括贡献拆分、预处理前缀信息与高效离线查询。

下列代码是区间逆序对的实现，当 $q=O(n)$ 时，总复杂度为 $O(n\sqrt{n})$ 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
int cl = 1, cr = 0;
vector<queryl> qsl;
vector<queryr> qsr;
for (int i = 0; i < m; i++) {
    auto [_,ql, qr, qi] = qs[i];
    if (cl > ql) qsl.emplace_back(1, cr, ql, cl - 1, i), cl = ql;
    if (cr < qr) qsr.emplace_back(1, cl, cr + 1, qr, i), cr = qr;
    if (cl < ql) qsl.emplace_back(-1, cr, cl, ql - 1, i), cl = ql;
    if (cr > qr) qsr.emplace_back(-1, cl, qr + 1, cr, i), cr = qr;
}
ranges::sort(qsl, [](auto &x, auto &y) { return x.r > y.r; });
ranges::sort(qsr, [](auto &x, auto &y) { return x.l < y.l; });

cl = 0, cr = n + 1;
Block<int> bl(maxv + 1), br(maxv + 1);
for (auto &[op, ql, rs, re, qi]: qsr) {
    while (cl < ql - 1) br.add(maxv + 1 - a[++cl], 1);
    for (int i = rs; i <= re; i++) {
        qs[qi].ans += (f[i] - br.sum(maxv - a[i])) * op;
    }
}
for (auto &[op, qr, ls, le, qi]: qsl) {
    while (cr > qr + 1) bl.add(a[--cr], 1);
    for (int i = ls; i <= le; i++) {
        qs[qi].ans += (g[i] - bl.sum(a[i] - 1)) * op;
    }
}