「算法笔记」分块算法

分块算法,和莫队有着异曲同工之妙,是一种优雅的暴力。


概述

分块算法,顾名思义是把一个长度为 $n$ 的序列分成 $m$ 块,每块的大小均为 $\frac{n}{m}$。我们维护块内信息,使得块内信息的查询是 $\mathcal O(1)$ 的,而总的询问又可以看做是若干个块的询问的总和。

为了方便描述,我们定义:

  • 完整块:区间操作时,完整包含于区间的块。
  • 不完整的块:区间操作时,只有部分包含于区间的块,即左右端点所在的两个块。
  • 零散元素:不完整的块内的元素。

我们发现,对于一个询问 $[l, r]$,我们可以进行如下处理:

  • 拆成若干个完整块,其中每个完整快内的信息可以 $\mathcal O(1)$ 更新。其中完整块的数量为 $\mathcal O(\frac{n}{m})$。
  • 剩下两个不完整的块,对于这两个块内的信息暴力更新。其中不完整的块的大小为 $\mathcal O(m)$。

综上所述,分块算法单次操作的时间复杂度为 $\mathcal O(\frac{n}{m}+m)$。根据均值不等式,我们可以发现 $m=\sqrt n$ 时复杂度最优。


如何分块

我们定义如下变量:

$len$$num$$bl[i]$$l[i]$$r[i]$
块的大小块的数量第 $i$ 个元素所属的块第 $i$ 个块的左端点第 $i$ 个块的右端点

那么我们可以用如下代码建立分块:

其中特别需要注意 r[num] = n 意味着第 $num$ 个块(最后一个块)的右端点一定是 $n$!

void build() {
    len = sqrt(n), num = (n - 1) / len + 1;
    for (int i = 1; i <= n; i++) {
        bl[i] = (i - 1) / len + 1;
    }
    for (int i = 1; i <= num; i++) {
        l[i] = (i - 1) * len + 1, r[i] = i * len;
    }
    r[num] = n;
}

接下来我们就用 $9​$ 个来自 LOJ 的例题(可能稍有修改)来简单讲解一下分块的思想。


例题 1

给定一个长度为 $n$ 的序列和 $m$ 个操作。支持区间加法,单点求值。

Solution

我们用 $tag[i]$ 记录第 $i$ 个块内每个元素都加的值。

对于修改操作 $[x, y]$ 有两种情况:

  • 其中 $x$ 和 $y$ 在同一个块内,那么直接暴力修改 $a[i]$ 的值即可。
  • 其中 $x$ 和 $y$ 不在同一个块内,那么先修改整块 $(bl[x], bl[y])$ 的 $tag$ 值,然后再对 $x$ 和 $y$ 所在的块内的零散元素暴力修改 $a[i]$ 的值。

对于查询操作 $x$,直接输出 $a[x] + tag[bl[x]]$ 的值。

时间复杂度:$\mathcal O(m\sqrt n)$

Code

#include <cstdio>
#include <cmath>

const int N = 1e5 + 5, M = 320;

int n, m, len, num, a[N], bl[N], l[M], r[M], tag[M];

void build() {
    len = sqrt(n), num = (n - 1) / len + 1;
    for (int i = 1; i <= n; i++) {
        bl[i] = (i - 1) / len + 1;
    }
    for (int i = 1; i <= num; i++) {
        l[i] = (i - 1) * len + 1, r[i] = i * len;
    }
    r[num] = n;
}
void modify(int x, int y, int v) {
    if (bl[x] == bl[y]) {
        for (int i = x; i <= y; i++) a[i] += v;
    } else {
        for (int i = bl[x] + 1; i <= bl[y] - 1; i++) tag[i] += v;
        for (int i = x; i <= r[bl[x]]; i++) a[i] += v;
        for (int i = l[bl[y]]; i <= y; i++) a[i] += v;
    }
}
int query(int x) {
    return a[x] + tag[bl[x]];
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }
    build();
    for (int i = 1; i <= m; i++) {
        int opt;
        scanf("%d", &opt);
        if(!opt) {
            int x, y, v;
            scanf("%d%d%d", &x, &y, &v);
            modify(x, y, v);
        } else {
            int x;
            scanf("%d", &x);
            printf("%d\n", query(x));
        }
    }
    return 0;
}

例题 2

给定一个长度为 $n$ 的序列和 $m$ 个操作。支持区间加法,区间查询小于 $v$ 的元素个数。

Solution

我们首先考虑没有修改操作怎么做:

  • 对于零散元素,我们直接暴力查找。
  • 对于整块,我们可以先排序然后直接二分查找。

如果有了修改操作,那么意味着我们每次修改后需要重新排序,还是分成两部分考察:

  • 对于零散元素,我们暴力修改后对不完整块直接重新排序。时间复杂度为 $\mathcal O(\sqrt n\log n)$。
  • 对于整块,我们发现修改不影响元素之间的相对顺序,所以不需要排序。查询时需要用 $v - tag[i]$ 的值二分查找。时间复杂度为 $\mathcal O(\sqrt n)$。

时间复杂度:$\mathcal O(m\sqrt n\log n)$(其中可以用均值不等式计算出更优的复杂度 QAQ)

Code

#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>

const int N = 1e5 + 5, M = 320;

int n, m, len, num, a[N], bl[N], l[M], r[M], tag[M];
std::vector<int> ve[M];

void build() {
    len = sqrt(n), num = (n - 1) / len + 1;
    for (int i = 1; i <= n; i++) {
        bl[i] = (i - 1) / len + 1;
        ve[bl[i]].push_back(a[i]);
    }
    for (int i = 1; i <= num; i++) {
        l[i] = (i - 1) * len + 1, r[i] = i * len;
        std::sort(ve[i].begin(), ve[i].end());
    }
    r[num] = n;
}
void reset(int x) {
    ve[x].clear();
    for (int i = l[x]; i <= r[x]; i++) ve[x].push_back(a[i]);
    std::sort(ve[x].begin(), ve[x].end());
}
void modify(int x, int y, int v) {
    if (bl[x] == bl[y]) {
        for (int i = x; i <= y; i++) a[i] += v;
        reset(bl[x]);
    } else {
        for (int i = bl[x] + 1; i <= bl[y] - 1; i++) tag[i] += v;
        for (int i = x; i <= r[bl[x]]; i++) a[i] += v;
        for (int i = l[bl[y]]; i <= y; i++) a[i] += v;
        reset(bl[x]), reset(bl[y]);
    }
}
int query(int x, int y, int v) {
    int ans = 0;
    if (bl[x] == bl[y]) {
        for (int i = x; i <= y; i++) {
            if (a[i] + tag[bl[i]] < v) ans++;
        }
    } else {
        for (int i = bl[x] + 1; i <= bl[y] - 1; i++) {
            ans += std::lower_bound(ve[i].begin(), ve[i].end(), v - tag[i]) - ve[i].begin();
        }
        for (int i = x; i <= r[bl[x]]; i++) {
            if (a[i] + tag[bl[i]] < v) ans++;
        }
        for (int i = l[bl[y]]; i <= y; i++) {
            if (a[i] + tag[bl[i]] < v) ans++;
        }
    }
    return ans;
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }
    build();
    for (int i = 1; i <= m; i++) {
        int opt, x, y, v;
        scanf("%d%d%d%d", &opt, &x, &y, &v);
        if(!opt) {
            modify(x, y, v);
        } else {
            printf("%d\n", query(x, y, v));
        }
    }
    return 0;
}

例题 3

给定一个长度为 $n$ 的序列和 $m$ 个操作。支持区间加法,区间查询 $v$ 的前驱。

Solution

我们有一个很直观的想法:直接沿用例题 2 的思路,只要修改一下二分即可。

但是这题有一个更简单的方法,直接用 $\text{set}$ 维护块内信息。这样甚至可以支持插入和删除操作,更加方便。但是 $\text{set}$ 常数巨大,所以此题不建议使用 $\text{set}​$ 来维护。

时间复杂度:$\mathcal O(m\sqrt n\log n)$

Code

直接二分查找

#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>

const int N = 1e5 + 5, M = 320;

int n, m, len, num, a[N], bl[N], l[M], r[M], tag[M];
std::vector<int> ve[M];

void build() {
    len = sqrt(n), num = (n - 1) / len + 1;
    for (int i = 1; i <= n; i++) {
        bl[i] = (i - 1) / len + 1;
        ve[bl[i]].push_back(a[i]);
    }
    for (int i = 1; i <= num; i++) {
        l[i] = (i - 1) * len + 1, r[i] = i * len;
        std::sort(ve[i].begin(), ve[i].end());
    }
    r[num] = n;
}
void reset(int x) {
    ve[x].clear();
    for (int i = l[x]; i <= r[x]; i++) ve[x].push_back(a[i]);
    std::sort(ve[x].begin(), ve[x].end());
}
void modify(int x, int y, int v) {
    if (bl[x] == bl[y]) {
        for (int i = x; i <= y; i++) a[i] += v;
        reset(bl[x]);
    } else {
        for (int i = bl[x] + 1; i <= bl[y] - 1; i++) tag[i] += v;
        for (int i = x; i <= r[bl[x]]; i++) a[i] += v;
        for (int i = l[bl[y]]; i <= y; i++) a[i] += v;
        reset(bl[x]), reset(bl[y]);
    }
}
int query(int x, int y, int v) {
    int ans = -1;
    if (bl[x] == bl[y]) {
        for (int i = x; i <= y; i++) {
            int val = a[i] + tag[bl[i]];
            if (val < v) ans = std::max(ans, val);
        }
    } else {
        for (int i = bl[x] + 1; i <= bl[y] - 1; i++) {
            std::vector<int>::iterator it = std::lower_bound(ve[i].begin(), ve[i].end(), v - tag[i]);
            if (it != ve[i].begin()) ans = std::max(ans, *(--it) + tag[i]);
        }
        for (int i = x; i <= r[bl[x]]; i++) {
            int val = a[i] + tag[bl[i]];
            if (val < v) ans = std::max(ans, val);
        }
        for (int i = l[bl[y]]; i <= y; i++) {
            int val = a[i] + tag[bl[i]];
            if (val < v) ans = std::max(ans, val);
        }
    }
    return ans;
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    build();
    for (int i = 1; i <= m; i++) {
        int opt, x, y, v;
        scanf("%d%d%d%d", &opt, &x, &y, &v);
        if(!opt) {
            modify(x, y, v);
        } else {
            printf("%d\n", query(x, y, v));
        }
    }
    return 0;
}

使用 $\text{set}$ 维护

#include <cstdio>
#include <cmath>
#include <algorithm>
#include <set>

const int N = 1e5 + 5, M = 320;

int n, m, len, num, a[N], bl[N], l[M], r[M], tag[M];
std::set<int> s[M];

void build() {
    len = sqrt(n), num = (n - 1) / len + 1;
    for (int i = 1; i <= n; i++) {
        bl[i] = (i - 1) / len + 1;
        s[bl[i]].insert(a[i]);
    }
    for (int i = 1; i <= num; i++) {
        l[i] = (i - 1) * len + 1, r[i] = i * len;
    }
    r[num] = n;
}
void update(int x, int v) {
    s[bl[x]].erase(a[x]), s[bl[x]].insert(a[x] += v);
}
void modify(int x, int y, int v) {
    if (bl[x] == bl[y]) {
        for (int i = x; i <= y; i++) update(i, v);
    } else {
        for (int i = bl[x] + 1; i <= bl[y] - 1; i++) tag[i] += v;
        for (int i = x; i <= r[bl[x]]; i++) update(i, v);
        for (int i = l[bl[y]]; i <= y; i++) update(i, v);
    }
}
int query(int x, int y, int v) {
    int ans = -1;
    if (bl[x] == bl[y]) {
        for (int i = x; i <= y; i++) {
            int val = a[i] + tag[bl[i]];
            if (val < v) ans = std::max(ans, val);
        }
    } else {
        for (int i = bl[x] + 1; i <= bl[y] - 1; i++) {
            std::set<int>::iterator it = s[i].lower_bound(v - tag[i]);
            if (it != s[i].begin()) ans = std::max(ans, *(--it) + tag[i]);
        }
        for (int i = x; i <= r[bl[x]]; i++) {
            int val = a[i] + tag[bl[i]];
            if (val < v) ans = std::max(ans, val);
        }
        for (int i = l[bl[y]]; i <= y; i++) {
            int val = a[i] + tag[bl[i]];
            if (val < v) ans = std::max(ans, val);
        }
    }
    return ans;
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }
    build();
    for (int i = 1; i <= m; i++) {
        int opt, x, y, v;
        scanf("%d%d%d%d", &opt, &x, &y, &v);
        if(!opt) {
            modify(x, y, v);
        } else {
            printf("%d\n", query(x, y, v));
        }
    }
    return 0;
}

例题 4

给定一个长度为 $n$ 的序列和 $m$ 个操作。支持区间加法,区间求和。答案对 $10^9 + 7$ 取模。

Solution

这题还是和例题 1 一样的思路,只不过需要多维护一个区间和:我们定义 $sum[i]$ 表示第 $i$ 个块的总和(不包括 $tag[i]$ 的值,也就是说这两者是独立的)。

我们先分析修改操作,对于两种情况分类讨论:

  • 对于零散元素,我们暴力修改 $a[i]$ 和 $sum[bl[i]]$ 的值。
  • 对于整块,只需要修改 $tag[i]$ 的值即可,而不需要修改 $sum[i]$ 的值。

我们再分析查询操作,对于两种情况分类讨论:

  • 对于零散元素,我们用 $a[i] + tag[bl[i]]$ 来更新答案。
  • 对于整块,经过简单的思考就可以发现答案就是 $sum[i] + tag[i]\times len$ 的总和。

为什么可以直接用 $len$ 的值?因为我们在统计时,只使用 $(bl[x], bl[y])$ 这个闭区间内的整块,不涉及最后一个块,所以每个块的大小必为 $len$。

时间复杂度:$\mathcal O(m\sqrt n)$

Code

#include <cstdio>
#include <cmath>

const int N = 1e5 + 5, M = 320;
const int mod = 1e9 + 7;

int n, m, len, num, a[N], bl[N], l[M], r[M], tag[M], sum[M];

void add(int &x, int y) {
    (x += y) >= mod && (x -= mod);
}
void build() {
    len = sqrt(n), num = (n - 1) / len + 1;
    for (int i = 1; i <= n; i++) {
        bl[i] = (i - 1) / len + 1;
        add(sum[bl[i]], a[i]);
    }
    for (int i = 1; i <= num; i++) {
        l[i] = (i - 1) * len + 1, r[i] = i * len;
    }
    r[num] = n;
}
void modify(int x, int y, int v) {
    if (bl[x] == bl[y]) {
        for (int i = x; i <= y; i++) a[i] += v;
        add(sum[bl[x]], 1LL * (y - x + 1) * v % mod);
    } else {
        for (int i = bl[x] + 1; i <= bl[y] - 1; i++) add(tag[i], v);
        for (int i = x; i <= r[bl[x]]; i++) add(a[i], v);
        add(sum[bl[x]], 1LL * (r[bl[x]] - x + 1) * v % mod);
        for (int i = l[bl[y]]; i <= y; i++) add(a[i], v);
        add(sum[bl[y]], 1LL * (y - l[bl[y]] + 1) * v % mod);
    }
}
int query(int x, int y) {
    int ans = 0;
    if (bl[x] == bl[y]) {
        for (int i = x; i <= y; i++) add(ans, a[i]);
        add(ans, 1LL * (y - x + 1) * tag[bl[x]] % mod);
    } else {
        for (int i = bl[x] + 1; i <= bl[y] - 1; i++) {
            add(ans, sum[i]);
            add(ans, 1LL * tag[i] * len % mod);
        }
        for (int i = x; i <= r[bl[x]]; i++) add(ans, a[i]);
        add(ans, 1LL * (r[bl[x]] - x + 1) * tag[bl[x]] % mod);
        for (int i = l[bl[y]]; i <= y; i++) add(ans, a[i]);
        add(ans, 1LL * (y - l[bl[y]] + 1) * tag[bl[y]] % mod);
    }
    return ans;
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }
    build();
    for (int i = 1; i <= m; i++) {
        int opt, x, y;
        scanf("%d%d%d", &opt, &x, &y);
        if(!opt) {
            int v;
            scanf("%d", &v);
            modify(x, y, v);
        } else {
            printf("%d\n", query(x, y));
        }
    }
    return 0;
}

例题 5

给定一个长度为 $n$ 的序列和 $m$ 个操作。支持区间开方,区间求和。

Solution

由于有区间开方操作,没法直接更新区间和,问题貌似比较棘手。

但是我们可以分析一下开方的性质:一个 $10^9$ 的数字不断进行开方,其值大约为:$10^9, 31622, 177, 13, 3, 1, 1, 1, \cdots$

那么意味着,每个数最多被开方大约 $5$ 次,这样我们可以记录每个块中是否有 $>1$ 的元素。如果没有则不需要对这个块内元素开方操作。

有了这个性质,直接暴力操作即可。

时间复杂度:$\mathcal O(m\sqrt n)$

Code

#include <cstdio>
#include <cmath>

const int N = 1e5 + 5, M = 320;

int n, m, len, num, a[N], bl[N], l[M], r[M], sum[M];
bool flg[M];

void build() {
    len = sqrt(n), num = (n - 1) / len + 1;
    for (int i = 1; i <= n; i++) {
        bl[i] = (i - 1) / len + 1;
        sum[bl[i]] += a[i];
    }
    for (int i = 1; i <= num; i++) {
        l[i] = (i - 1) * len + 1, r[i] = i * len;
    }
    r[num] = n;
}
void solve(int x) {
    if (flg[x]) return;
    sum[x] = 0, flg[x] = 1;
    for (int i = l[x]; i <= r[x]; i++) {
        sum[x] += (a[i] = sqrt(a[i]));
        flg[x] &= (a[i] <= 1);
    }
}
void modify(int x, int y) {
    if (bl[x] == bl[y]) {
        for (int i = x; i <= y; i++) {
            sum[bl[x]] -= a[i];
            sum[bl[x]] += (a[i] = sqrt(a[i]));
        }
    } else {
        for (int i = bl[x] + 1; i <= bl[y] - 1; i++) solve(i);
        for (int i = x; i <= r[bl[x]]; i++) {
            sum[bl[x]] -= a[i];
            sum[bl[x]] += (a[i] = sqrt(a[i]));
        }
        for (int i = l[bl[y]]; i <= y; i++) {
            sum[bl[y]] -= a[i];
            sum[bl[y]] += (a[i] = sqrt(a[i]));
        }
    }
}
int query(int x, int y) {
    int ans = 0;
    if (bl[x] == bl[y]) {
        for (int i = x; i <= y; i++) ans += a[i];
    } else {
        for (int i = bl[x] + 1; i <= bl[y] - 1; i++) ans += sum[i];
        for (int i = x; i <= r[bl[x]]; i++) ans += a[i];
        for (int i = l[bl[y]]; i <= y; i++) ans += a[i];
    }
    return ans;
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    build();
    for (int i = 1; i <= m; i++) {
        int opt, x, y;
        scanf("%d%d%d", &opt, &x, &y);
        if(!opt) {
            modify(x, y);
        } else {
            printf("%d\n", query(x, y));
        }
    }
    return 0;
}

例题 6

给定一个长度为 $n$ 的序列和 $m$ 个操作。支持单点插入,单点求值。

Solution

首先考虑数据随机的情况,那么每个块内插入的操作是均摊的。我们只需要用 $\text{vector}$ 维护每个块,暴力插入查询即可,时间复杂度依旧为 $\mathcal O(m\sqrt n)$。

我们发现,在极限数据下,某个块内可能会被插入至多 $\mathcal O(m)$ 次,这样单次操作的复杂度就变成了 $\mathcal O(m)$,显然是不能接受的。

我们发现,当一个块的大小过大时就会影响整体的复杂度。那么我们在块过大时进行重构分块,我们定义一个阈值 $k$,当某个块的大小超过 $k\times len$ 时,我们对整个序列进行重构。一般而言,这个阈值 $k$ 在 $20$ 左右复杂度较优。

当然还有一个方法:每进行 $\sqrt n$ 次插入操作后就进行重构。每次重构的复杂度为 $\mathcal O(n + m)$,那么总体的复杂度还是 $\mathcal O(m\sqrt n)$(默认 $n$ 和 $m$ 同阶)。

时间复杂度:$\mathcal O(m\sqrt n)$

Code

#include <cstdio>
#include <cmath>
#include <vector>

const int N = 1e5 + 5, M = 500;

int n, m, len, num, a[N], st[N << 1];
std::vector<int> ve[M];

void build() {
    len = sqrt(n), num = (n - 1) / len + 1;
    for (int i = 1; i <= n; i++) {
        ve[(i - 1) / len + 1].push_back(a[i]);
    }
}
void rebuild() {
    int top = 0;
    for (int i = 1; i <= num; i++) {
        for (int j = 0; j < (int)ve[i].size(); j++) {
            st[++top] = ve[i][j];
        }
        ve[i].clear();
    }
    len = sqrt(top), num = (top - 1) / len + 1;
    for (int i = 1; i <= top; i++) {
        ve[(i - 1) / len + 1].push_back(st[i]);
    }
}
std::pair<int, int> get(int k) {
    int x = 1;
    while (k > (int)ve[x].size()) k -= ve[x++].size();
    return std::make_pair(x, k - 1);
}
void insert(int x, int v) {
    std::pair<int, int> r = get(x);
    int i = r.first;
    ve[i].insert(ve[i].begin() + r.second, v);
    if ((int)ve[i].size() > 20 * len) rebuild();
}
int query(int x) {
    std::pair<int, int> r = get(x);
    return ve[r.first][r.second];
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }
    build();
    for (int i = 1; i <= m; i++) {
        int opt, x;
        scanf("%d%d", &opt, &x);
        if(!opt) {
            int v;
            scanf("%d", &v);
            insert(x, v);
        } else {
            printf("%d\n", query(x));
        }
    }
    return 0;
}

例题 7

给定一个长度为 $n$ 的序列和 $m$ 个操作。支持区间乘法,区间加法,单点求值。答案对 $10007$ 取模。

Solution

我们发现修改操作和「Luogu 3373」【模板】线段树 2 的套路非常相似。

首先我们强制乘法比加法优先。也就是说,块内维护两个标记 $add[i]$ 和 $mul[i]$ 分别表示整个块内加、乘的值。一个元素 $a[i]$ 实际表示的值为 $a[i]\times mul[bl[i]]+add[bl[i]]$。

  • 块内乘法 $v$:假如两个标记的值为 $A$ 和 $M$,那么标记变成 $A\times v$ 和 $M\times v$。
  • 块内加法 $v$:假如两个标记的值为 $A$ 和 $M$,那么标记变成 $A + v$ 和 $M$。

对于零散元素,我们无法直接修改,所以直接暴力将所在块内的标记转移到元素上,然后将标记清空($add[i] = 0, mul[i] = 1$),直接对零散元素本身修改即可。

时间复杂度:$\mathcal O(m \log n)$。

Code

#include <cstdio>
#include <cmath>

const int N = 1e5 + 5, M = 320;
const int mod = 10007;

int n, m, len, num, a[N], bl[N], l[M], r[M], add[M], mul[M];

void build() {
    len = sqrt(n), num = (n - 1) / len + 1;
    for (int i = 1; i <= n; i++) {
        bl[i] = (i - 1) / len + 1;
    }
    for (int i = 1; i <= num; i++) {
        l[i] = (i - 1) * len + 1, r[i] = i * len, mul[i] = 1;
    }
    r[num] = n;
}
void add(int &x, int y) {
    (x += y) >= mod && (x-=mod);
}
void reset(int x) {
    for (int i = l[x]; i <= r[x]; i++) {
        a[i] = (a[i] * mul[x] + add[x]) % mod;
    }
    add[x] = 0, mul[x] = 1;
}
void modifyAdd(int x, int y, int v) {
    if (bl[x] == bl[y]) {
        reset(bl[x]);
        for (int i = x; i <= y; i++) add(a[i], v);
    } else {
        for (int i = bl[x] + 1; i <= bl[y] - 1; i++) add(add[i], v);
        reset(bl[x]), reset(bl[y]);
        for (int i = x; i <= r[bl[x]]; i++) add(a[i], v);
        for (int i = l[bl[y]]; i <= y; i++) add(a[i], v);
    }
}
void modifyMul(int x, int y, int v) {
    if (bl[x] == bl[y]) {
        reset(bl[x]);
        for (int i = x; i <= y; i++) (a[i] *= v) %= mod;
    } else {
        for (int i = bl[x] + 1; i <= bl[y] - 1; i++) {
            (add[i] *= v) %= mod, (mul[i] *= v) %= mod;
        }
        reset(bl[x]), reset(bl[y]);
        for (int i = x; i <= r[bl[x]]; i++) (a[i] *= v) %= mod;
        for (int i = l[bl[y]]; i <= y; i++) (a[i] *= v) %= mod;
    }
}
int query(int x) {
    return (a[x] * mul[bl[x]] + add[bl[x]]) % mod;
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }
    build();
    for (int i = 1; i <= m; i++) {
        int opt;
        scanf("%d", &opt);
        if(!opt) {
            int x, y, v;
            scanf("%d%d%d", &x, &y, &v);
            modifyAdd(x, y, v % mod);
        } else if (opt == 1) {
            int x, y, v;
            scanf("%d%d%d", &x, &y, &v);
            modifyMul(x, y, v % mod);
        } else {
            int x;
            scanf("%d", &x);
            printf("%d\n", query(x));
        }
    }
    return 0;
}

例题 8

给定一个长度为 $n$ 的序列和 $m$ 个操作。支持区间查询等于 $v$ 的元素个数并覆盖为 $v$。

Solution

我们先考虑一个暴力的做法,对于修改操作:

  • 对于零散元素,我们暴力修改。注意单点修改前需要下放标记
  • 对于整块,我们对这个块打上标记,表示整个块内的元素相同,均为 $v$。

然后考虑查询操作:

  • 对于零散元素,我们下放标记后暴力查询。
  • 对于整块,如果这个块内有标记且标记的值为 $v$,那么对答案有 $len$ 的贡献。如果没有标记,那么我们对 $[l[i], r[i]]$ 区间内的元素暴力查询

这个做法看上去单次查询的复杂度为 $\mathcal O(n)$,但是我们这样分析:

假设初始序列都是同一个值,那么单次查询的复杂度为 $\mathcal O(\sqrt n)$。如果这是进行一个区间操作,它最多破环首位 $2$ 个块的标记,所以只能使得后面的询问至多增加 $2$ 个块的暴力时间,所以均摊的单次复杂度为 $\mathcal O(\sqrt n)$。

换句话说,要让一次操作耗费 $\mathcal O(n)$ 的时间,要先花费 $\mathcal O(\sqrt n)$ 个操作对数列进行修改!综上所述,总体时间复杂度为 $\mathcal O(m\sqrt n)$。

时间复杂度:$\mathcal O(m\sqrt n)$

Code

#include <cstdio>
#include <cmath>

const int N = 1e5 + 5, M = 320;

int n, m, len, num, a[N], bl[N], l[M], r[M], cov[M];
bool tag[M];

void build() {
    len = sqrt(n), num = (n - 1) / len + 1;
    for (int i = 1; i <= n; i++) {
        bl[i] = (i - 1) / len + 1;
    }
    for (int i = 1; i <= num; i++) {
        l[i] = (i - 1) * len + 1, r[i] = i * len;
    }
    r[num] = n;
}
void reset(int x) {
    if(!tag[x]) return;
    for (int i = l[x]; i <= r[x]; i++) a[i] = cov[x];
    tag[x] = 0;
}
void modify(int x, int y, int v) {
    if (bl[x] == bl[y]) {
        reset(bl[x]);
        for (int i = x; i <= y; i++) a[i] = v;
    } else {
        for (int i = bl[x] + 1; i <= bl[y] - 1; i++) {
            tag[i] = 1, cov[i] = v;
        }
        reset(bl[x]), reset(bl[y]);
        for (int i = x; i <= r[bl[x]]; i++) a[i] = v;
        for (int i = l[bl[y]]; i <= y; i++) a[i] = v;
    }
}
int query(int x, int y, int v) {
    int ans = 0;
    if (bl[x] == bl[y]) {
        reset(bl[x]);
        for (int i = x; i <= y; i++) ans += (a[i] == v);
    } else {
        for (int i = bl[x] + 1; i <= bl[y] - 1; i++) {
            if (tag[i]) {
                ans += (cov[i] == v ? len : 0);
            } else {
                for (int j = l[i]; j <= r[i]; j++) ans += (a[j] == v);
            }
        }
        reset(bl[x]), reset(bl[y]);
        for (int i = x; i <= r[bl[x]]; i++) ans += (a[i] == v);
        for (int i = l[bl[y]]; i <= y; i++) ans += (a[i] == v);
    }
    return ans;
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }
    build();
    for (int i = 1; i <= m; i++) {
        int x, y, v;
        scanf("%d%d%d", &x, &y, &v);
        printf("%d\n", query(x, y, v));
        modify(x, y, v);
    }
    return 0;
}

例题 9

给定一个长度为 $n$ 的序列和 $m​$ 个操作。支持区间查询最小众数。

Solution

以下解法中,我们为了方便表述,定义 $\text{mode}(i)$ 表示第 $i$ 个整块的众数。

解法 1(无修改)

我们首先可以发现一个性质:对于询问 $[x, y]$,答案 $\in\text{mode}(i\sim j)\cup\text{零散元素}$(其中 $\text{mode}(i\sim j$) 表示 $[x, y]$ 内的所有整块的众数)。令 $l, r$ 分别在第 $a, b$ 块,那么 $[l, r]$ 可以拆成:

  • 从 $l$ 到第 $a$ 块的最后一个元素。
  • 从第 $a + 1$ 块到第 $b - 1​$ 块。
  • 从第 $b$ 块的起始一个元素到 $r$。

根据这个性质,我们只需要至多比较 $2\sqrt n + 1​$ 即 $\mathcal O(\sqrt n)​$ 个数的出现次数即可。

那么我们可以 $\mathcal O(n\sqrt n)$ 预处理 $f[i][j]$ 表示第 $i$ 个整块到第 $j$ 个整块的众数。然后对于每个种值开一个 $\text{vector}$ 记录值 $i$ 出现的位置。

接下来考虑询问 $[x, y]$ 怎么分解处理:

  • 对于零散元素,我们暴力查找每个元素在 $[x, y]​$ 内的出现次数,这个过程可以通过在记录 $a[i]​$ 出现位置的 $ve[a[i]]​$ 内二分查找实现。
  • 对于整块,众数为 $f[bl[x] + 1][bl[y] - 1]$,出现次数同理可以二分得到。

我们只需要在这 $\mathcal O(\sqrt n)$ 个数内找到出现次数最多的数即可。

注意,为了方便计算需要事先对数据离散化

时间复杂度:$\mathcal O(m\sqrt n\log n)$,可以通过均值不等式计算出块的大小为 $\sqrt{\frac{n}{\log n}}$ 以获得更优的复杂度通过本题。

期望得分:$80\sim 100​$

解法 2(无修改)

我们考虑在解法 1 的基础上进行修改。首先 $\sqrt n$ 这个系数是肯定没法去掉了,考虑如何仍然在 $\sqrt n$ 分块下去掉 $\log n$ 这个系数。这意味着我们要在 $\mathcal O(1)$ 的时间内回答询问。

不妨设 $F[i][x]$ 表示 $[0, i]$ 之间有多少个 $x$。那么 $[l, r]$ 之间的 $x$ 的数量就是 $F[r][x] - F[l - 1][x]$,所以可以省去一个二分的 $\log n$。

预处理时,我们只需要对序列扫一遍即可,复杂度为 $\mathcal O(n)​$。

时间复杂度:$\mathcal O(m\sqrt n)$

期望得分:$100$

解法 3(带修改)

貌似可以 $\sqrt[3] n$ 分块?推荐阅读 区间众数解题报告 - 陈立杰 改日填坑

Code

解法 1

#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <vector>

const int N = 1e5 + 5, M = 1300;

int n, m, len, num, a[N], val[N], bl[N], l[M], r[M], cnt[N], f[M][M];
std::vector<int> p[N];

void build() {
    for (int i = 1; i <= n; i++) val[i] = a[i];
    std::sort(val + 1, val + n + 1);
    int sz = std::unique(val + 1, val + n + 1) - (val + 1);
    for (int i = 1; i <= n; i++) {
        a[i] = std::lower_bound(val + 1, val + sz + 1, a[i]) - val;
        p[a[i]].push_back(i);
    }
    len = sqrt(n / log2(n)), num = (n - 1) / len + 1;
    for (int i = 1; i <= n; i++) {
        bl[i] = (i - 1) / len + 1;
    }
    for (int i = 1; i <= num; i++) {
        l[i] = (i - 1) * len + 1, r[i] = i * len;
    }
    r[num] = n;
}
void init() {
    for (int i = 1; i <= num; i++) {
        memset(cnt, 0, sizeof(cnt));
        int ans = 0, mx = 0;
        for (int j = i; j <= num; j++) {
            for (int k = l[j]; k <= r[j]; k++) {
                cnt[a[k]]++;
                if (cnt[a[k]] > mx || (cnt[a[k]] == mx && a[k] < ans)) {
                    ans = a[k], mx = cnt[a[k]];
                }
            }
            f[i][j] = ans;
        }
    }
}
int sum(int l, int r, int v) {
    return std::upper_bound(p[v].begin(), p[v].end(), r) - std::lower_bound(p[v].begin(), p[v].end(), l);
}
void solve(int x, int y, int l, int r, int &ans, int &mx) {
    for (int i = x; i <= y; i++) {
        int now = sum(l, r, a[i]);
        if (now > mx || (now == mx && a[i] < ans)) {
            ans = a[i], mx = now;
        }
    }
}
int query(int x, int y) {
    int ans = 0, mx = 0;
    if (bl[x] + 1 >= bl[y]) {
        solve(x, y, x, y, ans, mx);
    } else {
        ans = f[bl[x] + 1][bl[y] - 1], mx = sum(x, y, ans);
        solve(x, r[bl[x]], x, y, ans, mx);
        solve(l[bl[y]], y, x, y, ans, mx);
    }
    return ans;
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }
    build(), init();
    for (int i = 1; i <= m; i++) {
        int x, y;
        scanf("%d%d", &x, &y);
        printf("%d\n", val[query(x, y)]);
    }
    return 0;
}

解法 2

// 改日填坑

解法 3

// 改日填坑

习题

  • Ynoi 吼啊!

发表评论