Leohh


Whatever the future brings, you are my light

【学习笔记】分块

2020-04-17 0条评论 619次阅读 1人点赞 Leohh

其实是复习笔记

复习一下「分块」数列分块入门1 – 9 by hzwer

T1：区间加法，单点查值

LOJ 6627 数列分块入门 1

做法：两边暴力加法，整块加法标记，复杂度 O(n\sqrt{n})​

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <math.h>
#define MAX_N 50005

using namespace std;

int n, blo;
int w[MAX_N];
int bl[MAX_N];
int tag[MAX_N];

void add(int a, int b, int x) {
    for (int i = a; i <= min(b, bl[a] * blo); i++) {
        w[i] += x;
    }
    if (bl[a] != bl[b]) {
        for (int i = (bl[b] - 1) * blo + 1; i <= b; i++) {
            w[i] += x;
        }
    }
    for (int i = bl[a] + 1; i < bl[b]; i++) {
        tag[i] += x;
    }
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", w + i);
    }
    blo = (int)sqrt(n) + 1;
    for (int i = 1; i <= n; i++) {
        bl[i] = (i - 1) / blo + 1;
    }
    int op, x, y, z;
    for (int i = 1; i <= n; i++) {
        scanf("%d%d%d%d", &op, &x, &y, &z);
        if (op == 0) {
            add(x, y, z);
        } else {
            printf("%d\n", w[y] + tag[bl[y]]);
        }
    }
}

T2：区间加法，区间查询小于某个值的元素个数

LOJ 6278 数列分块入门 2

做法：每个整块开个vector，里面排好序。两边暴力统计并重建vector，整块顺序不变，查询时lower_bound，复杂度 O(n\sqrt{n}\log{\sqrt{n}})​

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <vector>
#define MAX_N 50005
#define L(x) ((bl[x] - 1) * blo + 1)
#define R(x) (bl[x] * blo)
#define LB(x) (((x)-1) * blo + 1)
#define RB(x) ((x)*blo)

using namespace std;

int n, blo;
int w[MAX_N];
int bl[MAX_N];
int tag[MAX_N];
vector<int> v[MAX_N];

void bsort(int b) {
    v[b].clear();
    for (int i = LB(b); i <= min(n, RB(b)); i++) {
        v[b].push_back(w[i]);
    }
    sort(v[b].begin(), v[b].end());
}

void add(int a, int b, int x) {
    for (int i = a; i <= min(b, R(a)); i++) {
        w[i] += x;
    }
    bsort(bl[a]);
    if (bl[a] != bl[b]) {
        for (int i = L(b); i <= b; i++) {
            w[i] += x;
        }
        bsort(bl[b]);
    }
    for (int i = bl[a] + 1; i < bl[b]; i++) {
        tag[i] += x;
    }
}

int getans(int a, int b, int x) {
    int cnt = 0;
    for (int i = a; i <= min(b, R(a)); i++) {
        cnt += (w[i] + tag[bl[a]] < x);
    }
    if (bl[a] != bl[b]) {
        for (int i = L(b); i <= b; i++) {
            cnt += (w[i] + tag[bl[b]] < x);
        }
    }
    for (int i = bl[a] + 1; i < bl[b]; i++) {
        cnt += (lower_bound(v[i].begin(), v[i].end(), x - tag[i]) - v[i].begin());
    }
    return cnt;
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", w + i);
    }
    blo = (int)sqrt(n) + 1;
    for (int i = 1; i <= n; i++) {
        bl[i] = (i - 1) / blo + 1;
    }
    for (int i = 1; i <= bl[n]; i++) {
        bsort(i);
    }
    int op, x, y, z;
    for (int i = 1; i <= n; i++) {
        scanf("%d%d%d%d", &op, &x, &y, &z);
        if (op == 0) {
            add(x, y, z);
        } else {
            printf("%d\n", getans(x, y, z * z));
        }
    }
}

T3：区间加法，区间查询某个值的前驱

做法：同T2

LOJ 6279 数列分块入门 3

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <vector>
#define MAX_N 100005
#define L(x) ((bl[x] - 1) * blo + 1)
#define R(x) (bl[x] * blo)
#define LB(x) (((x)-1) * blo + 1)
#define RB(x) ((x)*blo)

using namespace std;

int n, blo;
int w[MAX_N];
int bl[MAX_N];
int tag[MAX_N];
vector<int> v[MAX_N];

void bsort(int b) {
    v[b].clear();
    for (int i = LB(b); i <= min(n, RB(b)); i++) {
        v[b].push_back(w[i]);
    }
    sort(v[b].begin(), v[b].end());
}

void add(int a, int b, int x) {
    for (int i = a; i <= min(b, R(a)); i++) {
        w[i] += x;
    }
    bsort(bl[a]);
    if (bl[a] != bl[b]) {
        for (int i = L(b); i <= b; i++) {
            w[i] += x;
        }
        bsort(bl[b]);
    }
    for (int i = bl[a] + 1; i < bl[b]; i++) {
        tag[i] += x;
    }
}

int getans(int a, int b, int x) {
    int ans = -1;
    for (int i = a; i <= min(b, R(a)); i++) {
        if (w[i] + tag[bl[a]] < x) {
            ans = max(ans, w[i] + tag[bl[a]]);
        }
    }
    if (bl[a] != bl[b]) {
        for (int i = L(b); i <= b; i++) {
            if (w[i] + tag[bl[b]] < x) {
                ans = max(ans, w[i] + tag[bl[b]]);
            }
        }
    }
    for (int i = bl[a] + 1; i < bl[b]; i++) {
        int t = lower_bound(v[i].begin(), v[i].end(), x - tag[i]) - v[i].begin();
        if (t > 0) {
            ans = max(ans, v[i][t - 1] + tag[i]);
        }
    }
    return ans;
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", w + i);
    }
    blo = (int)sqrt(n) + 1;
    for (int i = 1; i <= n; i++) {
        bl[i] = (i - 1) / blo + 1;
    }
    for (int i = 1; i <= bl[n]; i++) {
        bsort(i);
    }
    int op, x, y, z;
    for (int i = 1; i <= n; i++) {
        scanf("%d%d%d%d", &op, &x, &y, &z);
        if (op == 0) {
            add(x, y, z);
        } else {
            printf("%d\n", getans(x, y, z));
        }
    }
}

T4：区间加法，区间求和

LOJ 6280 数列分块入门 4

做法：每个整块记录全体增加的值和整块总和（不算全体增加的值），两边暴力维护，复杂度 O(n\sqrt{n})​

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <math.h>
#define MAX_N 50005
#define L(x) ((bl[x] - 1) * blo + 1)
#define R(x) (bl[x] * blo)
#define LB(x) (((x)-1) * blo + 1)
#define RB(x) ((x)*blo)
#define int long long

using namespace std;

int n, blo;
int w[MAX_N];
int bl[MAX_N];
int sum[MAX_N];
int tag[MAX_N];

void add(int a, int b, int x) {
    for (int i = a; i <= min(b, R(a)); i++) {
        w[i] += x, sum[bl[a]] += x;
    }
    if (bl[a] != bl[b]) {
        for (int i = L(b); i <= b; i++) {
            w[i] += x, sum[bl[b]] += x;
        }
    }
    for (int i = bl[a] + 1; i < bl[b]; i++) {
        tag[i] += x;
    }
}

int getsum(int a, int b, int p) {
    int ans = 0;
    for (int i = a; i <= min(b, R(a)); i++) {
        ans = (ans + w[i] + tag[bl[a]]) % p;
    }
    if (bl[a] != bl[b]) {
        for (int i = L(b); i <= b; i++) {
            ans = (ans + w[i] + tag[bl[b]]) % p;
        }
    }
    for (int i = bl[a] + 1; i < bl[b]; i++) {
        ans = (ans + sum[i] + tag[i] * blo % p) % p;
    }
    return ans;
}

signed main() {
    scanf("%lld", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%lld", w + i);
    }
    blo = (int)sqrt(n) + 1;
    for (int i = 1; i <= n; i++) {
        bl[i] = (i - 1) / blo + 1;
        sum[bl[i]] += w[i];
    }
    int op, x, y, z;
    for (int i = 1; i <= n; i++) {
        scanf("%lld%lld%lld%lld", &op, &x, &y, &z);
        if (op == 0) {
            add(x, y, z);
        } else {
            printf("%lld\n", getsum(x, y, z + 1));
        }
    }
}

T5：区间开方，区间求和

LOJ 6281 数列分块入门 5

做法：有性质「大于1的数经过不超过5次开方后会变成1，0无论怎样开方都是0」，所以记录一下每个块是否是全0/1，对于不是全0/1的块暴力开方，复杂度 O(n\sqrt{n})

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <math.h>
#define MAX_N 50005
#define L(x) ((bl[x] - 1) * blo + 1)
#define R(x) (bl[x] * blo)
#define LB(x) (((x)-1) * blo + 1)
#define RB(x) ((x)*blo)

using namespace std;

int n, blo;
int w[MAX_N];
int bl[MAX_N];
int sum[MAX_N];
int cnt[MAX_N];

void sqrts(int a, int b) {
    for (int i = a; i <= b; i++) {
        sum[bl[i]] -= w[i];
        cnt[bl[i]] -= (w[i] <= 1);
        w[i] = sqrt(w[i]);
        sum[bl[i]] += w[i];
        cnt[bl[i]] += (w[i] <= 1);
    }
}

void upd(int a, int b) {
    sqrts(a, min(b, R(a)));
    if (bl[a] != bl[b]) {
        sqrts(L(b), b);
    }
    for (int i = bl[a] + 1; i < bl[b]; i++) {
        if (cnt[i] < blo) {
            sqrts(LB(i), RB(i));
        }
    }
}

int getsum(int a, int b) {
    int ans = 0;
    for (int i = a; i <= min(b, R(a)); i++) {
        ans += w[i];
    }
    if (bl[a] != bl[b]) {
        for (int i = L(b); i <= b; i++) {
            ans += w[i];
        }
    }
    for (int i = bl[a] + 1; i < bl[b]; i++) {
        ans += sum[i];
    }
    return ans;
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", w + i);
    }
    blo = (int)sqrt(n) + 1;
    for (int i = 1; i <= n; i++) {
        bl[i] = (i - 1) / blo + 1;
        sum[bl[i]] += w[i];
        cnt[bl[i]] += (w[i] <= 1);
    }
    int op, x, y, z;
    for (int i = 1; i <= n; i++) {
        scanf("%d%d%d%d", &op, &x, &y, &z);
        if (op == 0) {
            upd(x, y);
        } else {
            printf("%d\n", getsum(x, y));
        }
    }
}

T6：单点插入，单点查询

LOJ 6282 数列分块入门 6

做法：每插入 \sqrt{n} 次，重新 O(n)​ 建块，总复杂度 O(n\sqrt{n})

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <vector>
#define MAX_N 200005

using namespace std;

int n, blo, cnt;
int w[MAX_N];
vector<int> v[MAX_N];

void ins(int k, int x) {
    for (int i = 1; i <= cnt; i++) {
        if (k <= v[i].size()) {
            v[i].insert(v[i].begin() + (k - 1), x);
            return;
        }
        k -= v[i].size();
    }
}

int getans(int k) {
    for (int i = 1; i <= cnt; i++) {
        if (k <= v[i].size()) {
            return v[i][k - 1];
        }
        k -= v[i].size();
    }
    return 0;
}

void rebuild() {
    int tot = 0;
    for (int i = 1; i <= cnt; i++) {
        for (int j = 0; j < v[i].size(); j++) {
            w[++tot] = v[i][j];
        }
        v[i].clear();
    }
    blo = (int)sqrt(tot) + 1;
    for (int i = 1; i <= tot; i++) {
        cnt = (i - 1) / blo + 1;
        v[cnt].push_back(w[i]);
    }
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", w + i);
    }
    blo = (int)sqrt(n) + 1;
    for (int i = 1; i <= n; i++) {
        cnt = (i - 1) / blo + 1;
        v[cnt].push_back(w[i]);
    }
    int op, x, y, z, c = 0;
    for (int i = 1; i <= n; i++) {
        scanf("%d%d%d%d", &op, &x, &y, &z);
        if (op == 0) {
            ins(x, y);
            if (++c >= (int)sqrt(n) + 1) {
                rebuild();
                c = 0;
            }
        } else {
            printf("%d\n", getans(y));
        }
    }
}

T7：区间加法，区间乘法，单点查值

LOJ 6283 数列分块入门 7

做法：整块记录加法和乘法标记（先乘后加），两边先暴力重置所在块的标记，然后再暴力修改

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <math.h>
#define MAX_N 100005
#define MOD 10007
#define L(x) ((bl[x] - 1) * blo + 1)
#define R(x) (bl[x] * blo)
#define LB(x) (((x)-1) * blo + 1)
#define RB(x) ((x)*blo)

using namespace std;

int n, blo;
int w[MAX_N];
int bl[MAX_N];
int ta[MAX_N];
int tm[MAX_N];

void reset(int b) {
    for (int i = LB(b); i <= min(n, RB(b)); i++) {
        w[i] = (w[i] * tm[b] + ta[b]) % MOD;
    }
    ta[b] = 0, tm[b] = 1;
}

void add(int a, int b, int x) {
    reset(bl[a]);
    for (int i = a; i <= min(b, R(a)); i++) {
        w[i] = (w[i] + x) % MOD;
    }
    if (bl[a] != bl[b]) {
        reset(bl[b]);
        for (int i = L(b); i <= b; i++) {
            w[i] = (w[i] + x) % MOD;
        }
    }
    for (int i = bl[a] + 1; i < bl[b]; i++) {
        ta[i] = (ta[i] + x) % MOD;
    }
}

void mul(int a, int b, int x) {
    reset(bl[a]);
    for (int i = a; i <= min(b, R(a)); i++) {
        w[i] = w[i] * x % MOD;
    }
    if (bl[a] != bl[b]) {
        reset(bl[b]);
        for (int i = L(b); i <= b; i++) {
            w[i] = w[i] * x % MOD;
        }
    }
    for (int i = bl[a] + 1; i < bl[b]; i++) {
        ta[i] = ta[i] * x % MOD;
        tm[i] = tm[i] * x % MOD;
    }
}

int getans(int k) {
    return (w[k] * tm[bl[k]] + ta[bl[k]]) % MOD;
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", w + i);
    }
    blo = (int)sqrt(n) + 1;
    for (int i = 1; i <= n; i++) {
        bl[i] = (i - 1) / blo + 1;
    }
    for (int i = 1; i <= bl[n]; i++) {
        tm[i] = 1;
    }
    int op, x, y, z;
    for (int i = 1; i <= n; i++) {
        scanf("%d%d%d%d", &op, &x, &y, &z);
        if (op == 0) {
            add(x, y, z);
        } else if (op == 1) {
            mul(x, y, z);
        } else {
            printf("%d\n", getans(y));
        }
    }
}

T8：区间询问等于某个值的元素个数，并同时将该区间所有数改为该值

LOJ 6284 数列分块入门 8

做法：

每个整块记录一下这个块是否被全体置为某个值。

修改时，对于两边所在的块，如果有全置标记，则将标记暴力下放到每个元素上，然后再暴力修改；对于整块，直接修改该块的全置标记。

查询时，如果没有全置标记就暴力查询，有的话就 O(1)​ 判断。

复杂度分析：

先假设一开始所有的数都是同一个值

每次修改操作显然是 O(\sqrt{n}) 的，并且每次修改操作至多会为接下来增加2倍的「暴力单块查询复杂度」即 O(\sqrt{n})

而除去暴力单块查询的区间查询操作的单次复杂度为 O(\sqrt{n})

所以该假设下的总复杂度为 O(n\sqrt{n})​

而将假设「一开始所有的数都是同一个值」变为题中的情况，相当于一开始全部数都一样，然后做了 n 次修改操作，所以除去假设后的复杂度还是 O(n\sqrt{n})

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <math.h>
#define MAX_N 100005
#define L(x) ((bl[x] - 1) * blo + 1)
#define R(x) (bl[x] * blo)
#define LB(x) (((x)-1) * blo + 1)
#define RB(x) ((x)*blo)

using namespace std;

int n, blo;
int w[MAX_N];
int bl[MAX_N];
int tag[MAX_N];

void reset(int b) {
    if (tag[b] != -1) {
        for (int i = LB(b); i <= min(n, RB(b)); i++) {
            w[i] = tag[b];
        }
        tag[b] = -1;
    }
}

void upd(int a, int b, int x) {
    reset(bl[a]);
    for (int i = a; i <= min(b, R(a)); i++) {
        w[i] = x;
    }
    if (bl[a] != bl[b]) {
        reset(bl[b]);
        for (int i = L(b); i <= b; i++) {
            w[i] = x;
        }
    }
    for (int i = bl[a] + 1; i < bl[b]; i++) {
        tag[i] = x;
    }
}

int getblo(int b, int x) {
    int cnt = 0;
    for (int i = LB(b); i <= min(n, RB(b)); i++) {
        cnt += (w[i] == x);
    }
    tag[b] = x;
    return cnt;
}

int getans(int a, int b, int x) {
    int ans = 0;
    for (int i = a; i <= min(b, R(a)); i++) {
        ans += (tag[bl[a]] == x || (tag[bl[a]] == -1 && w[i] == x));
    }
    if (bl[a] != bl[b]) {
        for (int i = L(b); i <= b; i++) {
            ans += (tag[bl[b]] == x || (tag[bl[b]] == -1 && w[i] == x));
        }
    }
    for (int i = bl[a] + 1; i < bl[b]; i++) {
        if (tag[i] != -1) {
            ans += blo * (tag[i] == x);
        } else {
            ans += getblo(i, x);
        }
    }
    return ans;
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", w + i);
    }
    blo = (int)sqrt(n) + 1;
    for (int i = 1; i <= n; i++) {
        bl[i] = (i - 1) / blo + 1;
    }
    memset(tag, -1, sizeof(tag));
    int x, y, z;
    for (int i = 1; i <= n; i++) {
        scanf("%d%d%d", &x, &y, &z);
        printf("%d\n", getans(x, y, z));
        upd(x, y, z);
    }
}

T9：离线区间众数

LOJ 6285 数列分块入门 9

用莫队写更方便一些，所以这里就咕了qwq

本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可
点赞
最后编辑：2020-04-17

发表评论

电子邮件地址不会被公开。必填项已用 * 标注