57 · 根号分治与莫队入门

这一节的两件事看上去无关：一件是“把能整除的小模数全部预处理”，一件是“把询问排序后暴力挪指针”。它们的共同动作是往复杂度里塞一个 √n——用 √n 次廉价操作，换掉一次昂贵操作。

形态一：按参数大小分治。以 P3396 为例。询问参数是模数 x：x 小的组合少（x ≤ T 时一共只有 Σx ≈ T²/2 张表），可以全部预存；x 大的时候池子里的数少（最多 n/x 个），现场跳着扫也不贵。取 T = √n，两种分支的代价都是 √n：查询 O(1) 或 O(√n)，修改 O(√n)。

形态二：按规模分治。信这句话：一个长度为 n 的序列里，出现次数 > T 的值至多 n/T 个。于是把出现多的叫“重值”，只给重值做预处理（前缀出现次数表，代价 O(n·n/T)），出现少的“轻值”整串不超过 T 次，询问时直接枚举它的出现位置。树上同理：度数 > √m 的点至多 √m 个，这是虚树、分块图的第一步。

形态二和莫队是同一件事的两种外壳：都在用“总量有限”来给最坏情况封顶。形态一说“小的种类少”，形态二说“大的个数少”，两者相乘一定不超过 n。

先把三个语法零件拆开：阈值与两套分支、四个指针的移动、带奇偶优化的排序。

#include <bits/stdc++.h>
using namespace std;

const int N = 150005, T = 400;
int n = 10, a[N], s[T + 5][T + 5];

int main() {
    for (int i = 1; i <= n; ++i) a[i] = i;          // 假装输入是 1 2 3 ... 10

    for (int x = 1; x <= T; ++x)                    // 建表：只给小模数建
        for (int i = 1; i <= n; ++i)
            s[x][i % x] += a[i];

    int x = 2, y = 1, ans = 0;                      // 询问：模 2 余 1 的池子和
    if (x <= T) ans = s[x][y];                      // 小模数：O(1)
    else for (int i = y ? y : x; i <= n; i += x) ans += a[i];   // 大模数：O(n/T)

    cout << ans << "\n";                            // 1+3+5+7+9 = 25
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

int a[9] = {0, 1, 2, 2};                        // 只用 1..3 号位置，值域 1..2
int cnt[9];
long long cur = 0;                              // 维护 Σ cnt²

void add(int p) { cur += 2LL * cnt[a[p]] + 1; ++cnt[a[p]]; }
void del(int p) { cur -= 2LL * cnt[a[p]] - 1; --cnt[a[p]]; }

int main() {
    int L = 1, R = 0;                           // 空区间
    int l = 1, r = 3;                           // 目标区间 [1, 3] = {1, 2, 2}
    while (L > l) add(--L);
    while (R < r) add(++R);
    while (L < l) del(L++);
    while (R > r) del(R--);
    cout << cur << "\n";                        // 1² + 2² = 5
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

struct Query { int l, r, id; } q[6];
int B = 2;                                   // 块长：n/√m 的简化演示

bool cmp(const Query &x, const Query &y) {
    int bx = x.l / B, by = y.l / B;
    if (bx != by) return bx < by;             // 先按块
    return (bx & 1) ? x.r > y.r : x.r < y.r;  // 块内 r 的方向按块号奇偶翻转
}

int main() {
    int L[6] = {0, 1, 1, 3, 4, 5};
    int R[6] = {0, 5, 2, 6, 4, 8};
    for (int i = 1; i <= 5; ++i) { q[i].l = L[i]; q[i].r = R[i]; q[i].id = i; }
    sort(q + 1, q + 6, cmp);
    for (int i = 1; i <= 5; ++i) cout << q[i].l << " " << q[i].r << "\n";
    // 1 2 / 1 5 / 3 6 / 4 4 / 5 8：第 1、2 块 r 递增，第 3 块（奇数块）r 递减
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

const int N = 150005, T = 400;         // T ≈ √150000 ≈ 387，取整到 400
int n, m, a[N];
int s[T + 5][T + 5];                   // s[x][y]：所有 i ≡ y (mod x) 的 a[i] 之和，只存 x ≤ T

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= n; ++i) cin >> a[i];

    for (int x = 1; x <= T; ++x)                    // 建表：nT ≈ 6×10⁷ 次加法
        for (int i = 1; i <= n; ++i)
            s[x][i % x] += a[i];

    while (m--) {
        char op; int x, y;
        cin >> op >> x >> y;
        if (op == 'A') {
            if (x <= T) {
                cout << s[x][y] << "\n";            // 小模数：查表 O(1)
            } else {
                int r = 0;                          // 大模数：池内最多 n/x 个数，跳着扫
                for (int i = y ? y : x; i <= n; i += x) r += a[i];
                cout << r << "\n";
            }
        } else {
            for (int t = 1; t <= T; ++t)            // 改一个数，所有小模数的表都要动
                s[t][x % t] += y - a[x];
            a[x] = y;                               // 最后再改原数组，否则增量算错
        }
    }
    return 0;
}

现在换一个角度。前面是“按参数大小分工”，莫队是“按询问顺序分工”：把所有询问排个序，让相邻两个询问的区间尽量接近，然后暴力挪指针。单次询问是 O(n)，但相邻两次之间只挪一小段，总步数被摊平到 O(n√m)。

莫队有三个硬性前提，缺一不可：① 能离线（询问的答案与顺序无关）；② 维护的量在加入/删除一个元素时能 O(1) 更新；③ 区间能“增删元素”地维护，而不是只能整段重算。

#include <bits/stdc++.h>
using namespace std;

const int N = 100005;
int n, m, k, B;
int a[N], cnt[N];                  // cnt[v]：值 v 在当前区间里出现几次
long long cur, ans[N];             // cur = Σ cnt[v]²，最大 1e10，必须 long long

struct Query { int l, r, id; } q[N];

bool cmp(const Query &x, const Query &y) {
    int bx = x.l / B, by = y.l / B;
    if (bx != by) return bx < by;                     // 先按左端点所在块
    return (bx & 1) ? x.r > y.r : x.r < y.r;          // 块内 r 单调，奇偶块方向相反
}

void add(int p) { cur += 2LL * cnt[a[p]] + 1; ++cnt[a[p]]; }   // (c+1)² − c² = 2c + 1
void del(int p) { cur -= 2LL * cnt[a[p]] - 1; --cnt[a[p]]; }   // c² − (c−1)² = 2c − 1

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m >> k;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    B = max(1, (int)(n / sqrt(m)));            // 理论最优块长 n/√m
    for (int i = 1; i <= m; ++i) { cin >> q[i].l >> q[i].r; q[i].id = i; }
    sort(q + 1, q + m + 1, cmp);

    int L = 1, R = 0;                          // 当前维护的区间为空
    for (int i = 1; i <= m; ++i) {
        while (L > q[i].l) add(--L);           // 左端点外扩
        while (R < q[i].r) add(++R);           // 右端点外扩
        while (L < q[i].l) del(L++);           // 左端点内收
        while (R > q[i].r) del(R--);           // 右端点内收
        ans[q[i].id] = cur;                    // 此刻 [L, R] == [l, r]
    }

    for (int i = 1; i <= m; ++i) cout << ans[i] << "\n";
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

const int N = 100005;
int n, m, B;
int a[N], cnt[N];
int bad;                                    // 出现次数 >= 2 的值的个数
int ans[N];

struct Query { int l, r, id; } q[N];

bool cmp(const Query &x, const Query &y) {
    int bx = x.l / B, by = y.l / B;
    if (bx != by) return bx < by;
    return (bx & 1) ? x.r > y.r : x.r < y.r;     // 奇数块 r 倒序，省一趟回程
}

void add(int p) {
    if (++cnt[a[p]] == 2) ++bad;             // 1 -> 2：这个值开始重复
}

void del(int p) {
    if (cnt[a[p]] == 2) --bad;               // 2 -> 1：删掉后不再重复
    --cnt[a[p]];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    B = max(1, (int)(n / sqrt(m)));          // 理论最优块长 n/√m
    for (int i = 1; i <= m; ++i) { cin >> q[i].l >> q[i].r; q[i].id = i; }
    sort(q + 1, q + m + 1, cmp);

    int L = 1, R = 0;
    for (int i = 1; i <= m; ++i) {
        while (L > q[i].l) add(--L);
        while (R < q[i].r) add(++R);
        while (L < q[i].l) del(L++);
        while (R > q[i].r) del(R--);
        ans[q[i].id] = (bad == 0);
    }

    for (int i = 1; i <= m; ++i) cout << (ans[i] ? "Yes" : "No") << "\n";
    return 0;
}