首页 分类 学习 链接 关于
SITEMAP订阅

OI笔记 | 数列分块笔记

目录：

这是跟随 hzwer 学数列分块的笔记。黄学长太强了%%%。

一般来说，分块的通用性比线段树强，复杂度比线段树劣。

1(分块大小/复杂度分析方法)

LOJ 6277

要求支持区间加法，单点查值。

考虑把数列分为 $m$ 个块，则每个下标 $i$ 所属的块的编号为 $\lfloor \frac{i-1}{m}\rfloor +1$；编号为 $t$ 的块所表示的区间为 $[m(t-1)+1, mt]$。

对于区间加法，我们可以把不是整块的子区间暴力修改，最多要暴力改两个块，即 $O(m)$。是整块的子区间直接打上标记，打每个标记是 $O(1)$ 的，所以是 $O(\frac{n}{m})$。所以单次操作需要 $O(m+\frac{n}{m})$，根据均值不等式，$m+\frac{n}{m}\ge2\sqrt {n}$（当且仅当 $m=\sqrt{n}$ 时取等），所以块的个数取 $\sqrt{n}$ 最优。

总的时间复杂度为 $O(n\sqrt {n})$，其实比 $O(n\log n)$ 劣不少。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 50005;
int a[MAX_N], tag[MAX_N], bl[MAX_N], n, m;
inline ll read() {...}
inline void write(ll x) {...}
inline void update(int l, int r, int c) {
    for(int i = l; i <= min(bl[l] * m, r); i++) a[i] += c;
    if(bl[l] != bl[r])  for(int i = (bl[r] - 1) * m + 1; i <= r; i++)   a[i] += c;
    for(int i = bl[l] + 1; i <= bl[r] - 1; i++) tag[i] += c;
}
int main() {
    n = read(), m = sqrt(n);
    for(int i = 1; i <= n; i++) {
        bl[i] = (i - 1) / m + 1;
        a[i] = read();
    }
    for(int i = 1; i <= n; i++) {
        int op = read(), l = read(), r = read(), c = read();
        if(op == 0) update(l, r, c);
        else    write(a[r] + tag[bl[r]]), putchar('\n');
    }
    return 0;
}

2(块内排序/二分查找)

LOJ 6278

要求支持区间加法，询问区间小于 $x$ 的数的个数。

对于本题，虽然可能有比 $\sqrt{n}$ 更好的分块大小，但它已经足够优秀了。

先考虑查询。对于整块的子区间，我们可以预处理把每个块内排好序，然后二分查找第一个大于等于它的位置。对于非整块的子区间，暴力查询。所以单次查询总复杂度为 $O(\sqrt{n}\log \sqrt{n})$，主要是二分的复杂度。

再考虑修改。对于整块的子区间，用 $O(1)$ 修改标记即可。对于非整块的子区间，我们改完原值还要重新排序。单次修改总复杂度为 $O(\sqrt {n}\log \sqrt{n})$，主要是排序的复杂度。

总的时间复杂度是 $O(n\sqrt{n}\log \sqrt{n})$。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 50005;
int a[MAX_N], bl[MAX_N], tag[MAX_N], n, m;
vector<int> v[MAX_N];
inline ll read() {...}
inline void write(ll x) {...}
inline void reset(int t) {
    v[t].clear();
    for(int i = (t - 1) * m + 1; i <= min(t * m, n); i++)
        v[t].push_back(a[i]);
    sort(v[t].begin(), v[t].end());
}

inline void update(int l, int r, int c) {
    for(int i = l; i <= min(bl[l] * m, r); i++)
        a[i] += c;
    reset(bl[l]);
    if(bl[l] != bl[r]) {
        for(int i = (bl[r] - 1) * m + 1; i <= r; i++)
            a[i] += c;
        reset(bl[r]);
    }
    for(int i = bl[l] + 1; i <= bl[r] - 1; i++)
        tag[i] += c;
}
inline int query(int l, int r, int c) {
    int ret = 0;
    for(int i = l; i <= min(bl[l] * m, r); i++)
        if(a[i] + tag[bl[l]] < c)   ret++;
    if(bl[l] != bl[r])
        for(int i = (bl[r] - 1) * m + 1; i <= r; i++)
            if(a[i] + tag[bl[r]] < c)   ret++;
    for(int i = bl[l] + 1; i <= bl[r] - 1; i++)
        ret += lower_bound(v[i].begin(), v[i].end(), c - tag[i]) - v[i].begin();
    return ret;
}
int main() {
    n = read(), m = sqrt(n);
    for(int i = 1; i <= n; i++) {
        a[i] = read();
        bl[i] = (i - 1) / m + 1;
        v[bl[i]].push_back(a[i]);
    }
    for(int i = 1; i <= bl[n]; i++) sort(v[i].begin(), v[i].end());
    for(int i = 1; i <= n; i++) {
        int op = read(), l = read(), r = read(), c = read();
        if(op == 0) update(l, r, c);
        else    write(query(l, r, c * c)), putchar('\n');
    }
    return 0;
}

3(类似T2)

LOJ 6279

要求支持区间加法，询问区间小于 $x$ 的最大的数。

和上一题几乎一样。黄学长写的 std 是用 set 来维护一个块的，我用 set 写了一次却很奇怪地 TLE 了只有 $30pts$，可能常数要求比较高。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 1e5 + 10, MAX_M = 110;
int a[MAX_N], tag[MAX_N], bl[MAX_N], n, m;
vector<int> s[MAX_M];
inline ll read() {...}
inline void write(ll x) {...}
inline void reset(int x) {
    s[x].clear();
    for(int i = (x - 1) * m + 1; i <= min(x * m, n); i++)
        s[x].push_back(a[i]);
    sort(s[x].begin(), s[x].end());
}

inline void update(int l, int r, int c) {
    for(int i = l; i <= min(bl[l] * m, r); i++)
        a[i] += c;
    reset(bl[l]);
    if(bl[l] != bl[r]) {
        for(int i = (bl[r] - 1) * m + 1; i <= r; i++)
            a[i] += c;
        reset(bl[r]);
    }
    for(int i = bl[l] + 1; i <= bl[r] - 1; i++)
        tag[i] += c;
}
inline int query(int l, int r, int c) {
    int ret = -1;
    for(int i = l; i <= min(bl[l] * m, r); i++) {
        int v = a[i] + tag[bl[l]];
        if(v < c)    ret = max(ret, v);
    }
    if(bl[l] != bl[r]) {
        for(int i = (bl[r] - 1) * m + 1; i <= r; i++) {
            int v = a[i] + tag[bl[r]];
            if(v < c)   ret = max(ret, v);
        }
    }
    for(int i = bl[l] + 1; i <= bl[r] - 1; i++) {
        int pos = lower_bound(s[i].begin(), s[i].end(), c - tag[i]) - s[i].begin();
        if(pos >= 1)    ret = max(ret, s[i][pos - 1] + tag[i]);
    }
    return ret;
}

int main() {
    n = read(), m = 1000;
    for(int i = 1; i <= n; i++) {
        a[i] = read();
        bl[i] = (i - 1) / m + 1;
        s[bl[i]].push_back(a[i]);
    }
    for(int i = 1; i <= bl[n]; i++) sort(s[i].begin(), s[i].end());
    for(int i = 1; i <= n; i++) {
        int op = read(), l = read(), r = read(), c = read();
        if(op == 0) update(l, r, c);
        else    write(query(l, r, c)), putchar('\n');
    }
    return 0;
}

4(线段树1)

LOJ 6280

要求支持区间加法，区间求和。

我们维护每个块的和，暴力修改或查询不完整的块，区间求和时对完整的块可以直接加上 $sum_i+m\cdot tag_i$。

这题一定要开 long long。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 5e4 + 10, MAX_M = 305;
ll n, m, a[MAX_N], bl[MAX_N], tag[MAX_M], sum[MAX_M];

inline ll read() {...}
inline void write(ll x) {...}
inline void update(ll l, ll r, ll c) {
    for(int i = l; i <= min(bl[l] * m, r); i++)
        a[i] += c, sum[bl[l]] += c;
    if(bl[l] != bl[r]) 
        for(int i = (bl[r] - 1) * m + 1; i <= r; i++)
            a[i] += c, sum[bl[r]] += c;
    for(int i = bl[l] + 1; i <= bl[r] - 1; i++)
        tag[i] += c;
}
inline ll query(ll l, ll r) {
    ll ret = 0;
    for(int i = l; i <= min(bl[l] * m, r); i++)
        ret += a[i] + tag[bl[l]];
    if(bl[l] != bl[r])
        for(int i = (bl[r] - 1) * m + 1; i <= r; i++)
            ret += a[i] + tag[bl[r]];
    for(int i = bl[l] + 1; i <= bl[r] - 1; i++)
        ret += sum[i] + tag[i] * m;
    return ret;
}
int main() {
    n = read(), m = sqrt(n);
    for(int i = 1; i <= n; i++) {
        a[i] = read();
        bl[i] = (i - 1) / m + 1;
        sum[bl[i]] += a[i];
    }
    for(int i = 1; i <= n; i++) {
        ll op = read(), l = read(), r = read(), c = read();
        if(op == 0) update(l, r, c);
        else    write(query(l, r) % (c + 1)), putchar('\n');
    }
    return 0;
}

5(区间开方)

LOJ 6281

要求支持区间开方，区间求和。

这个之前用线段树做过。由于开方开多了会变成 $0$ 或 $1$，那么用线段树维护区间和的同时也维护最大值，如果区间最大值为 $1$ 就不用递归下去了。原题是 洛谷 P4145，线段树复杂度比分块优。

分块的话，我们暴力修改每一个块，然后记录这个块是否满足全是 $0$ 或 $1$，满足的话下次就不用暴力修改了。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 50005, MAX_M = 405;
int a[MAX_N], bl[MAX_N], sum[MAX_M], n, m;
bool flag[MAX_M];
inline ll read() {...}
inline void write(ll x) {...}

inline void update(int l, int r) {
    for(int i = l; i <= min(bl[l] * m, r); i++) {
        sum[bl[l]] -= a[i];
        a[i] = sqrt(a[i]);
        sum[bl[l]] += a[i];
    }
    if(bl[l] != bl[r]) {
        for(int i = (bl[r] - 1) * m + 1; i <= r; i++) {
            sum[bl[r]] -= a[i];
            a[i] = sqrt(a[i]);
            sum[bl[r]] += a[i];
        }
    }
    for(int i = bl[l] + 1; i <= bl[r] - 1; i++) {
        if(flag[i]) continue;
        flag[i] = 1, sum[i] = 0;
        for(int j = (i - 1) * m + 1; j <= i * m; j++) {
            a[j] = sqrt(a[j]), sum[i] += a[j];
            if(a[j] > 1)    flag[i] = 0;
        }
    }

}
inline int query(int l, int r) {
    int ret = 0;
    for(int i = l; i <= min(bl[l] * m, r); i++)
        ret += a[i];
    if(bl[l] != bl[r])
        for(int i = (bl[r] - 1) * m + 1; i <= r; i++)
            ret += a[i];
    for(int i = bl[l] + 1; i <= bl[r] - 1; i++)
        ret += sum[i];
    return ret;
}
int main() {
    n = read(), m = sqrt(n);
    for(int i = 1; i <= n; i++) {
        a[i] = read();
        bl[i] = (i - 1) / m + 1;
        sum[bl[i]] += a[i];
    }
    for(int i = 1; i <= n; i++) {
        int op = read(), l = read(), r = read(), c = read();
        if(op == 0) update(l, r);
        else    write(query(l, r)), putchar('\n');
    }
    return 0;
}

6(单点插入/重构)

LOJ 6282

要求支持单点插入，单点查值。

暴力的话最坏 $O(n^2)$。

每个块里面都用动态数组 vector，查值可以 $O(\sqrt{n})$ 查，插入的话先查到所在的块，再在块里插入，时间复杂度为 $O(v_i.size)$。 $v_i.size$ 的初值为 $\sqrt{n}$，但随着插入，在构造数据的情况下可能会变得很大。那么我们考虑当它过大的时候重新分块，复杂度可以接受。

记得重构时的临时数组要开两倍，否则插入的数会存不下。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX_N = 2e5 + 10, MAX_M = 1e4 + 10;
int n, siz, cnt, t[MAX_N];
vector<int> v[MAX_M];
inline ll read() {...}
inline void write(ll x) {...}

inline pii query(int pos) {
    int x = 1;
    while(pos > v[x].size())    pos -= v[x++].size();
    return (pii){x, pos - 1};
}

inline void rebuild() {
    int tp = 0;
    for(int i = 1; i <= cnt; i++) {
        for(auto j : v[i])
            t[++tp] = j;
        v[i].clear();
    }
    siz = sqrt(tp);
    for(int i = 1; i <= tp; i++)
        v[(i - 1) / siz + 1].push_back(t[i]);
    cnt = (tp - 1) / siz + 1;
}

inline void update(int pos, int x) {
    pii p = query(pos);
    v[p.first].insert(v[p.first].begin() + p.second, x);
    if(v[p.first].size() > 4000)
        rebuild();
}

int main() {
    n = read(), siz = sqrt(n);
    for(int i = 1; i <= n; i++) {
        int x = read();
        v[(i - 1) / siz + 1].push_back(x);
    }
    cnt = (n - 1) / siz + 1;
    for(int i = 1; i <= n; i++) {
        int op = read(), l = read(), r = read(), c = read();
        if(op == 0) update(l, r);
        else {
            pii p = query(r);
            write(v[p.first][p.second]), putchar('\n');
        }
    }
    return 0;
}

7(线段树2)

LOJ 6283

要求支持区间加法，区间乘法，单点询问。

其实就是第 $1$ 题加了个乘法标记，记得先乘后加，乘的时候加法标记也要乘。和线段树一样。

暴力修改的时候要先把所在的块的标记清空，否则会影响乘法标记的正确性。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 1e5 + 10, MAX_M = 500, MOD = 10007;
int n, m, a[MAX_N], bl[MAX_N], atag[MAX_M], mtag[MAX_M];
inline ll read() {...}
inline void write(ll x) {...}
inline void reset(int x) {
    for(int i = (x - 1) * m + 1; i <= min(x * m, n); i++) {
        (a[i] *= mtag[x]) %= MOD;
        (a[i] += atag[x]) %= MOD;
    }
    mtag[x] = 1, atag[x] = 0;
}
inline void update(int l, int r, int c, int op) {
    reset(bl[l]);
    for(int i = l; i <= min(bl[l] * m, r); i++) {
        if(op == 0) (a[i] += c) %= MOD;
        else    (a[i] *= c) %= MOD;
    }
    if(bl[l] != bl[r]) {
        reset(bl[r]);
        for(int i = (bl[r] - 1) * m + 1; i <= r; i++) {
            if(op == 0) (a[i] += c) %= MOD;
            else    (a[i] *= c) %= MOD;
        }
    }
    for(int i = bl[l] + 1; i <= bl[r] - 1; i++) {
        if(op == 0) (atag[i] += c) %= MOD;
        else {
            (mtag[i] *= c) %= MOD;
            (atag[i] *= c) %= MOD;
        }
    }
}
int main() {
    n = read(), m = sqrt(n);
    for(int i = 1; i <= n; i++) {
        a[i] = read();
        bl[i] = (i - 1) / m + 1;
    }
    for(int i = 1; i <= bl[n]; i++) mtag[i] = 1;
    for(int i = 1; i <= n; i++) {
        int op = read(), l = read(), r = read(), c = read();
        if(op < 2)  update(l, r, c, op);
        else    write((a[r] * mtag[bl[r]] + atag[bl[r]]) % MOD), putchar('\n');
    }
    return 0;
}

8(区间内等于某数的数的个数)

LOJ 6284

每次给定一个区间与一个数 $c$，询问区间内等于 $c$ 的数的个数，并把区间内所有数改成 $c$。

考虑暴力修改和查询。如果一个区间内只有一个数，我们只用改它的 $tag$。如果 $tag$ 为 $c$，直接加块的大小即可。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 1e5 + 10, MAX_M = 500;
int n, m, a[MAX_N], bl[MAX_N], tag[MAX_M];
inline ll read() {...}
inline void write(ll x) {...}

void reset(int x) {
    if(tag[x] != -1) {
        for(int i = (x - 1) * m + 1; i <= x * m; i++)
            a[i] = tag[x];
        tag[x] = -1;
    }
}

inline int solve(int l, int r, int c) {
    int ret = 0;
    reset(bl[l]);
    for(int i = l; i <= min(bl[l] * m, r); i++) {
        if(a[i] == c)   ret++;
        else    a[i] = c;
    }
    if(bl[l] != bl[r]) {
        reset(bl[r]);
        for(int i = (bl[r] - 1) * m + 1; i <= r; i++) {
            if(a[i] == c)   ret++;
            else    a[i] = c;
        }
    }
    for(int i = bl[l] + 1; i <= bl[r] - 1; i++) {
        if(tag[i] != -1) {
            if(tag[i] == c) ret += m;
            else    tag[i] = c;
        }
        else {
            for(int j = (i - 1) * m + 1; j <= i * m; j++) {
                if(a[j] == c)   ret++;
                else    a[j] = c;
            }
            tag[i] = c;
        }
    }
    return ret;
}   

int main() {
    n = read(), m = sqrt(n);
    for(int i = 1; i <= n; i++) {
        a[i] = read();
        bl[i] = (i - 1) / m + 1;    
    }
    for(int i = 1; i <= bl[n]; i++) tag[i] = -1;
    for(int i = 1; i <= n; i++) {
        int l = read(), r = read(), c = read();
        write(solve(l, r, c)), putchar('\n');
    }
    return 0;
}

9(区间众数的一种在线解法)

LOJ 6285

要求查询区间众数。

据说是经典难题。不过我抄的 hzwer 的代码，不得不感叹写的太妙了。分块大小改成了 $30$ 跑的挺快。原文说设为 $\sqrt{\frac{n}{\log n}}$ 最好，但是这是玄学。

首先对原数组离散化并分块，然后很方便地开桶预处理出所有 $f(i,j)(i\leq j)$ 即 $i$ 块到 $j$ 块之内的众数是多少。开一个二维 vector（记作 $v$），其中 $v_i$ 存下所有 $i$ 出现的下标。

对于每一次询问，初始化答案为 $f(bl_l+1, bl_r-1)$，然后暴力查询不完整的两个块中出现的数在 $[l,r]$ 内出现了多少次，这可以用二分查询，答案即为：

upper_bound(v[x].begin(), v[x].end(), r) - lower_bound(v[x].begin(), v[x].end(), l)

设分块大小为 $m$，当 $m$ 不太小时，时间复杂度大概是 $O(nm)$，主要是预处理带来的。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 1e5 + 10, MAX_M = 4000;
int n, m = 30, id;
int a[MAX_N], bl[MAX_N], f[MAX_M][MAX_M], val[MAX_N], cnt[MAX_N];
map<int, int> mp;
vector<int> v[MAX_N];

inline ll read() {...}
inline void write(ll x) {...}

inline void init(int x) {
    memset(cnt, 0, sizeof(cnt));
    int mx = 0, ans = 0;
    for(int i = (x - 1) * m + 1; i <= n; i++) {
        cnt[a[i]]++;
        if(cnt[a[i]] > mx || (cnt[a[i]] == mx && val[a[i]] < val[ans]))
            ans = a[i], mx = cnt[a[i]];
        f[x][bl[i]] = ans;
    }
}

inline int counts(int l, int r, int x) {return upper_bound(v[x].begin(), v[x].end(), r) - lower_bound(v[x].begin(), v[x].end(), l);}
inline int query(int l, int r) {
    int ans = f[bl[l] + 1][bl[r] - 1], mx = counts(l, r, ans);
    for(int i = l; i <= min(bl[l] * m, r); i++) {
        int t = counts(l, r, a[i]);
        if(t > mx || (t == mx && val[a[i]] < val[ans])) ans = a[i], mx = t;
    }
    if(bl[l] != bl[r]) {
        for(int i = (bl[r] - 1) * m + 1; i <= r; i++) {
            int t = counts(l, r, a[i]);
            if(t > mx || (t == mx && val[a[i]] < val[ans])) ans = a[i], mx = t;
        }
    }
    return val[ans];
}

int main() {
    n = read();
    for(int i = 1; i <= n; i++) {
        bl[i] = (i - 1) / m + 1;
        a[i] = read();
        if(!mp[a[i]])   mp[a[i]] = ++id, val[id] = a[i];
        a[i] = mp[a[i]];
        v[a[i]].push_back(i);
    }
    for(int i = 1; i <= bl[n]; i++) init(i);
    for(int i = 1; i <= n; i++) {
        int l = read(), r = read();
        write(query(l, r)), putchar('\n');
    }
    return 0;
}

这个解法是在线的，所以可以直接用于 洛谷 P4168。还有离线的时间复杂度更优的解法，如果之后遇到可以来补一下。

Published on Nov 16, 2022 in categories Note 

页面访问次数

♥

Joy © 2023 Powered by Jekyll and Theme by solid

今日诗词API Valine 评论管理 Github