前言

分块专题笔记。
根号是个好东西。

数列分块入门 1

题意简述

区间加、单点查。

解法

对每个大块记一个标记 flag，表示整个块内都加上了这么多数。
对于修改，左右小块暴力修，中间大块打标记。
查询直接输出即可。

#include <bits/stdc++.h>
using namespace std;
const int N = 5e4 + 15;
int n, m, t;
int a[N], flag[N];
int l[N], r[N], pos[N];

void add(int L, int R, int c) {
    int pl = pos[L], pr = pos[R];
    if (pl == pr) {
        for (int i = L; i <= R; i++) a[i] += c;
    } else {
        for (int i = L; i <= r[pl]; i++) a[i] += c;
        for (int i = l[pr]; i <= R; i++) a[i] += c;
        for (int i = pl + 1; i < pr; i++) flag[i] += c;
    }
}

int query(int x) {
    return flag[pos[x]] + a[x];
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    m = t = sqrt(n);
    for (int i = 1; i <= m; i++) l[i] = (i - 1) * t + 1, r[i] = i * t;
    if (r[m] < n) l[++m] = t * t + 1, r[m] = n;

    for (int i = 1; i <= m; i++)
        for (int j = l[i]; j <= r[i]; j++) pos[j] = i;
    ，
    for (int i = 1, op, l, r, c; i <= n; i++) {
        scanf("%d%d%d%d", &op, &l, &r, &c);
        if (op == 0) add(l, r, c);
        else printf("%d\n", query(r));
    }
    return 0;
}

数列分块入门 2

题意简述

求一个区间内 $\lt c^2$ 的数的个数，支持区间加。

解法

对于大块还是一样打加法标记，块内暴力修改。
块内维护一个排序后的序列，支持二分。
复杂度 $O(q \sqrt{n} \log \sqrt{n})$

#include <bits/stdc++.h>
using namespace std;
const int N = 5e4 + 15;
int n, m, t;
long long a[N], b[N], flag[N];
int l[N], r[N], pos[N];

void get(int x) {
    int L = l[x], R = r[x];
    for (int i = L; i <= R; i++) b[i] = a[i];
    sort(b + L, b + 1 + R);
}

void change(int L, int R, long long c) {
    int pl = pos[L], pr = pos[R];
    if (pl == pr) {
        for (int i = L; i <= R; i++) a[i] += c;
        get(pl);
    } else {
        for (int i = L; i <= r[pl]; i++) a[i] += c;
        get(pl);
        for (int i = l[pr]; i <= R; i++) a[i] += c;
        get(pr);
        for (int i = pl + 1; i < pr; i++) flag[i] += c;
    }
}

int query(int L, int R, long long c) {
    int pl = pos[L], pr = pos[R], cnt = 0;
    if (pl == pr) {
        for (int i = L; i <= R; i++) cnt += (a[i] + flag[pl]) < c;
    } else {
        for (int i = L; i <= r[pl]; i++) cnt += (a[i] + flag[pl]) < c;
        for (int i = l[pr]; i <= R; i++) cnt += (a[i] + flag[pr]) < c;
        for (int i = pl + 1; i < pr; i++) cnt += lower_bound(b + l[i], b + r[i] + 1, c - flag[i]) - b - l[i];
    }
    return cnt;
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    m = t = sqrt(n);
    for (int i = 1; i <= m; i++) l[i] = (i - 1) * t + 1, r[i] = i * t;
    if (r[m] < n) l[++m] = t * t + 1, r[m] = n;
    for (int i = 1; i <= m; i++)
        for (int j = l[i]; j <= r[i]; j++) pos[j] = i;

    for (int i = 1; i <= m; i++) get(i);

    for (int i = 1, op, l, r, c; i <= n; i++) {
        scanf("%d%d%d%d", &op, &l, &r, &c);
        if (op == 0) change(l, r, c);
        else printf("%d\n", query(l, r, c * 1ll * c));
    }
    return 0;
}

数列分块入门 3

题意简述

求区间前驱，支持区间加。

解法

和第二题不是一样吗。
查询的时候改一下就好了。
yysy，是不是要判一下负数，LOJ 数据是真弱。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 15; //没开够。
const int INF = 0x3f3f3f3f;
int n, m, t, a[N], b[N], flag[N];
int l[N], r[N], pos[N];

void get(int x) {
    int L = l[x], R = r[x];
    for (int i = L; i <= R; i++) b[i] = a[i];
    sort(b + L, b + 1 + R);
}

void change(int L, int R, long long c) {
    int pl = pos[L], pr = pos[R];
    if (pl == pr) {
        for (int i = L; i <= R; i++) a[i] += c;
        get(pl);
    } else {
        for (int i = L; i <= r[pl]; i++) a[i] += c;
        get(pl);
        for (int i = l[pr]; i <= R; i++) a[i] += c;
        get(pr);
        for (int i = pl + 1; i < pr; i++) flag[i] += c;
    }
}

int query(int L, int R, int c) {
    int pl = pos[L], pr = pos[R];
    if (pl == pr) {
        int Max = -INF;
        for (int i = L; i <= R; i++)
            if (a[i] + flag[pl] < c) Max = max(Max, a[i] + flag[pl]);
        return (Max == -INF) ? -1 : Max;
    } else {
        int Max = -INF;
        for (int i = L; i <= r[pl]; i++)
            if (a[i] + flag[pl] < c) Max = max(Max, a[i] + flag[pl]);
        for (int i = l[pr]; i <= R; i++)
            if (a[i] + flag[pr] < c) Max = max(Max, a[i] + flag[pr]);
        for (int i = pl + 1; i < pr; i++) {
            int id = lower_bound(b + l[i], b + r[i] + 1, c - flag[i]) - b;
            if (id - 1 >= l[i] && b[id - 1] < c) Max = max(Max, b[id - 1] + flag[i]);   //忘记加 flag 了。
        }
        return (Max == -INF) ? -1 : Max;
    }
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    m = t = sqrt(n);
    for (int i = 1; i <= m; i++) l[i] = (i - 1) * t + 1, r[i] = i * t;
    if (r[m] < n) l[++m] = t * t + 1, r[m] = n;
    for (int i = 1; i <= m; i++)
        for (int j = l[i]; j <= r[i]; j++) pos[j] = i;

    for (int i = 1; i <= m; i++) get(i);

    for (int i = 1, op, l, r, c; i <= n; i++) {
        scanf("%d%d%d%d", &op, &l, &r, &c);
        if (op == 0) change(l, r, c);
        else printf("%d\n", query(l, r, c));
    }
    return 0;
}

数列分块入门 4

题意简述

区间加、区间和。

解法

记录每个块的 sum。

#include <bits/stdc++.h>
using namespace std;
const int N = 5e4 + 15;
int n, m, t;
int a[N], flag[N];
long long sum[N];
int l[N], r[N], pos[N];

void add(int L, int R, int c) {
    int pl = pos[L], pr = pos[R];
    if (pl == pr) {
        for (int i = L; i <= R; i++) a[i] += c;
        sum[pl] += (R - L + 1) * 1ll * c;   //为什么我忘记更新 sum 了
    } else {
        for (int i = L; i <= r[pl]; i++) a[i] += c;
        sum[pl] += (r[pl] - L + 1) * 1ll * c;
        for (int i = l[pr]; i <= R; i++) a[i] += c;
        sum[pr] += (R - l[pr] + 1) * 1ll * c;
        for (int i = pl + 1; i < pr; i++) flag[i] += c;
    }
}

long long query(int L, int R, int mod) {
    int pl = pos[L], pr = pos[R];
    long long ans = 0;
    if (pl == pr) {
        for (int i = L; i <= R; i++) (ans += a[i] + flag[pl]) %= mod;
    } else {
        for (int i = L; i <= r[pl]; i++) (ans += a[i] + flag[pl]) %= mod;
        for (int i = l[pr]; i <= R; i++) (ans += a[i] + flag[pr]) %= mod;
        for (int i = pl + 1; i < pr; i++) (ans += sum[i] + flag[i] * 1ll * (r[i] - l[i] + 1)) %= mod;
    }
    return ans;
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    m = t = sqrt(n);
    for (int i = 1; i <= m; i++) l[i] = (i - 1) * t + 1, r[i] = i * t;
    if (r[m] < n) l[++m] = t * t + 1, r[m] = n;

    for (int i = 1; i <= m; i++)
        for (int j = l[i]; j <= r[i]; j++) pos[j] = i, sum[i] += a[j];

    for (int i = 1, op, l, r, c; i <= n; i++) {
        scanf("%d%d%d%d", &op, &l, &r, &c);
        if (op == 0) add(l, r, c);
        else printf("%lld\n", query(l, r, c + 1));
    }
    return 0;
}

数列分块入门 5

题意简述

区间开方，区间求和。

解法

注意到没有区间加！
所以一个数开方的次数是有限的，当区间最大值为 $1$ 时，就没有必要继续开方了，因为区间和不变。
所以当区间最大值大于 $1$，暴力修改；否则直接跳过。

#include <bits/stdc++.h>
using namespace std;
const int N = 5e4 + 15;
int n, m, t;
int a[N], flag[N], Max[N];
long long sum[N];
int l[N], r[N], pos[N];

void get(int x) {
    Max[x] = sum[x] = 0;
    for (int i = l[x]; i <= r[x]; i++) Max[x] = max(Max[x], a[i]), sum[x] += a[i];
}

void change(int L, int R) {
    int pl = pos[L], pr = pos[R];
    if (pl == pr) {
        for (int i = L; i <= R; i++) a[i] = sqrt(a[i]);
        get(pl);
    } else {
        for (int i = L; i <= r[pl]; i++) a[i] = sqrt(a[i]);
        get(pl);
        for (int i = l[pr]; i <= R; i++) a[i] = sqrt(a[i]);
        get(pr);
        for (int i = pl + 1; i < pr; i++) {
            if (Max[i] == 1) continue;
            for (int j = l[i]; j <= r[i]; j++) a[j] = sqrt(a[j]);
            get(i);
        }
    }
}

long long query(int L, int R) {
    int pl = pos[L], pr = pos[R];
    long long ans = 0;
    if (pl == pr) {
        for (int i = L; i <= R; i++) ans += a[i];
    } else {
        for (int i = L; i <= r[pl]; i++) ans += a[i];
        for (int i = l[pr]; i <= R; i++) ans += a[i];
        for (int i = pl + 1; i < pr; i++) ans += sum[i];
    }
    return ans;
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    m = t = sqrt(n);
    for (int i = 1; i <= m; i++) l[i] = (i - 1) * t + 1, r[i] = i * t;
    if (r[m] < n) l[++m] = t * t + 1, r[m] = n;

    for (int i = 1; i <= m; i++)
        for (int j = l[i]; j <= r[i]; j++) pos[j] = i, sum[i] += a[j];

    for (int i = 1, op, l, r, c; i <= n; i++) {
        scanf("%d%d%d%d", &op, &l, &r, &c);
        if (op == 0) change(l, r);
        else printf("%lld\n", query(l, r));
    }
    return 0;
}

数列分块入门 6

题意简述

单点插入、单点查询。

解法

思路类似块状链表。
记录 $2 \sqrt(n)$ 个数组，每个数组长度为 $2 \sqrt(n)$。
插入一个数就暴力移位，如果一个块长度大于二倍根号就全部重构。

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 15, M = 1015;
int n, a[N], b[N];
int p[M][M], sz[M], m, tot = 0;

void get() {
    tot = 0;
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= sz[i]; j++) b[++tot] = p[i][j];
}
void init() {   //重构块
    int t = sqrt(tot);
    for (int i = 1; i <= t + 1; i++) sz[i] = 0;
    for (int i = 1; i <= t; i++) {
        int l = (i - 1) * t + 1, r = i * t;
        for (int j = l; j <= r; j++) p[i][++sz[i]] = b[j];
    }
    m = t;
    if (t * t < n) {
        m++;
        for (int j = t * t + 1; j <= tot; j++) p[m][++sz[m]] = b[j];
    }
}

void insert(int x, int d) {
    tot++;
    if (x == tot) {
        p[m][++sz[m]] = d;
        if (sz[m] > 2 * sqrt(tot)) get(), init();
        return;
    }
    int id = 1, now = 0;
    while (now + sz[id] + 1 <= x) now += sz[id], id++;
    int pos = x - now;
    sz[id]++;
    for (int i = sz[id]; i >= pos + 1; i--) p[id][i] = p[id][i - 1];
    p[id][pos] = d;

    if (sz[id] > 2 * sqrt(tot)) get(), init();
}

int query(int x) {
    int id = 1, now = 0;
    while (now + sz[id] + 1 <= x) now += sz[id], id++;
    return p[id][x - now];
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]), b[i] = a[i];
    tot = n; init();

    for (int i = 1, op, l, r, c; i <= n; i++) {
        scanf("%d%d%d%d", &op, &l, &r, &c);
        if (op == 0) {
            insert(l, r);
        } else {
            printf("%d\n", query(r));
        }
        if (i == 6) break;
    }
    return 0;
}

数列分块入门 7

题意简述

区间加、区间乘、单点查。

解法

打两个懒标记，注意标记下传的顺序。本质上和线段树是一样的。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 15, mod = 10007;
int n, m, t;
int a[N], add[N], mul[N];
int l[N], r[N], pos[N];

void pushdown(int x) {
    for (int i = l[x]; i <= r[x]; i++) a[i] = ((a[i] * 1ll * mul[x] % mod) + add[x]) % mod;
    add[x] = 0, mul[x] = 1;
}

void Add(int L, int R, int c) {
    int pl = pos[L], pr = pos[R];
    pushdown(pl), pushdown(pr);
    if (pl == pr) {
        for (int i = L; i <= R; i++) (a[i] += c) %= mod;
    } else {
        for (int i = L; i <= r[pl]; i++) (a[i] += c) %= mod;
        for (int i = l[pr]; i <= R; i++) (a[i] += c) %= mod;
        for (int i = pl + 1; i < pr; i++) (add[i] += c) %= mod;
    }
}

void Mul(int L, int R, int c) {
    int pl = pos[L], pr = pos[R];
    pushdown(pl), pushdown(pr);
    if (pl == pr) {
        for (int i = L; i <= R; i++) (a[i] *= c) %= mod;
    } else {
        for (int i = L; i <= r[pl]; i++) (a[i] *= c) %= mod;
        for (int i = l[pr]; i <= R; i++) (a[i] *= c) %= mod;
        for (int i = pl + 1; i < pr; i++) (add[i] *= c) %= mod, (mul[i] *= c) %= mod;
    }
}

int query(int x) {
    return ((mul[pos[x]] * 1ll * a[x] % mod) + add[pos[x]]) % mod;
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]), a[i] %= mod;
    m = t = sqrt(n);
    for (int i = 1; i <= m; i++) l[i] = (i - 1) * t + 1, r[i] = i * t;
    if (r[m] < n) l[++m] = t * t + 1, r[m] = n;

    for (int i = 1; i <= m; i++) {
        add[i] = 0, mul[i] = 1;
        for (int j = l[i]; j <= r[i]; j++) pos[j] = i;
    }

    for (int i = 1, op, l, r, c; i <= n; i++) {
        scanf("%d%d%d%d", &op, &l, &r, &c);
        c %= mod;
        if (op == 0) Add(l, r, c);
        else if (op == 1) Mul(l, r, c);
        else printf("%d\n", query(r));
    }
    return 0;
}

数列分块入门 8

题意简述

区间查询个数，区间覆盖。

解法

二分查询左端点、右端点。
pushdown 覆盖之后不要写 get，复杂度会加一个 \log，警钟长鸣。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 15;
int n, m, t;
long long a[N], b[N], flag[N];
bool st[N];
int l[N], r[N], pos[N];

void get(int x) {
    int L = l[x], R = r[x];
    for (int i = L; i <= R; i++) b[i] = a[i];
    sort(b + L, b + 1 + R);
}

void pushdown(int x) {
    if (!st[x]) {
        get(x);
        return;
    }
    int L = l[x], R = r[x];
    for (int i = L; i <= R; i++) a[i] = flag[x];
    st[x] = 0, flag[x] = 0;
}

void change(int L, int R, int c) {
    int pl = pos[L], pr = pos[R];
    if (pl == pr) {
        for (int i = L; i <= R; i++) a[i] = c;
        get(pl);
    } else {
        for (int i = L; i <= r[pl]; i++) a[i] = c;
        get(pl);
        for (int i = l[pr]; i <= R; i++) a[i] = c;
        get(pr);
        for (int i = pl + 1; i < pr; i++) st[i] = 1, flag[i] = c;
    }
}

int query(int L, int R, int c) {
    int pl = pos[L], pr = pos[R], cnt = 0;
    if (pl == pr) {
        pushdown(pl);
        for (int i = L; i <= R; i++) cnt += (a[i] == c);
    } else {
        pushdown(pl), pushdown(pr);
        for (int i = L; i <= r[pl]; i++) cnt += (a[i] == c);
        for (int i = l[pr]; i <= R; i++) cnt += (a[i] == c);
        for (int i = pl + 1; i < pr; i++) {
            if (st[i]) {
                if (flag[i] == c) cnt += (r[i] - l[i] + 1);
                continue;
            }
            cnt += upper_bound(b + l[i], b + r[i] + 1, c) - lower_bound(b + l[i], b + r[i] + 1, c);
        }
    }
    return cnt;
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    m = t = sqrt(n);
    for (int i = 1; i <= m; i++) l[i] = (i - 1) * t + 1, r[i] = i * t;
    if (r[m] < n) l[++m] = t * t + 1, r[m] = n;
    for (int i = 1; i <= m; i++) {
        st[i] = 0, flag[i] = 0;
        for (int j = l[i]; j <= r[i]; j++) pos[j] = i;
    }

    for (int i = 1; i <= m; i++) get(i);

    for (int i = 1, l, r, c; i <= n; i++) {
        scanf("%d%d%d", &l, &r, &c);
        printf("%d\n", query(l, r, c));
        change(l, r, c);
    }
    return 0;
}

其他例题

P5046 【Ynoi2019 模拟赛】 Yuno loves sqrt technology I
以及 9。
以及 题单。