标签：入门分块 int void pos include 快速

基本思想

有一句老话，叫“大段维护，局部朴素”。

其实就是将一些东西人为的分为若干块，然后每个块整体的维护一些东西，小范围内直接暴力做，做到时空平衡。

其实和根号分治有点像。

然后整除分块和莫队我觉得和传统分块差别有点大了，就没写。

数列分块我一般的写法是维护每个位置所在块编号，块的左端点和块的右端点。

数列分块入门题

LOJ 数列分块入门 1

区间加，单点查。

维护区间整体增加了多少，修改的时候如果覆盖了整块就加到整块增量里去，否则直接加到数上。

查询就返回数组里的数+所在块的总体增量。

时间复杂度 \(O(N\sqrt N)\)。

#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 50005;
int len = 250, n, a[N];
int pos[N], add[N], L[N], R[N];
void init() {
    for (int i = 1; i <= n; i++) pos[i] = (i - 1) / len + 1;
    for (int i = 1; i <= n; i++) {
        if (pos[i] != pos[i - 1]) L[i] = i;
        else L[i] = L[i - 1];
    }
    for (int i = n; i >= 1; i--) {
        if (pos[i] != pos[i + 1]) R[i] = i;
        else R[i] = R[i + 1];
    }
}
void upd(int l, int r, int v) {
    if (pos[l] == pos[r]) {
        for (int i = l; i <= r; i++) a[i] += v;
        return ;
    }
    int p = pos[l] + 1, q = pos[r] - 1;
    for (int i = p; i <= q; i++) add[i] += v;
    for (int i = l; i <= R[l]; i++) a[i] += v;
    for (int i = L[r]; i <= r; i++) a[i] += v;
}
int qry(int p) {
    return a[p] + add[pos[p]];
}
int main(void) {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", a + i);
    init();
    for (int i = 1, op, l, r, c; i <= n; i++) {
        scanf("%d%d%d%d", &op, &l, &r, &c);
        if (op == 0) {
            upd(l, r, c);
        } else {
            printf("%d\n", qry(r));
        }
    }
    return 0;
}

LOJ 数列分块入门 2

区间加，查区间某元素排名。

还是储存整块的增量，一个位置实际的值就是访问到的+所在块的增量。

然后每块暴力预处理排一下序，修改的时候零散的也排序。每次修改最多排两次。

查询的话，对于整块的 lower_bound 一下，零散的一个一个数。

时间复杂度 \(O(N \sqrt n \log n)\)。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 50005;
int len = 250, n, a[N], cnt;
int pos[N], add[N], L[N], R[N], rnk[N];
void init() {
    for (int i = 1; i <= n; i++) pos[i] = (i - 1) / len + 1;
    cnt = pos[n];
    for (int i = 1; i <= cnt; i++) L[i] = (i - 1) * len + 1, R[i] = min(n, i * len);
    memmove(rnk, a, sizeof(int) * n);
    for (int i = 1; i <= cnt; i++) sort(rnk + L[i], rnk + R[i] + 1);
}
void upd(int l, int r, int v) {
    int p = pos[l], q = pos[r];
    if (p == q) {
        for (int i = l; i <= r; i++) a[i] += v;
        memmove(rnk + L[p], a + L[p], sizeof(int) * (R[p] - L[p] + 1));
        sort(rnk + L[p], rnk + R[q] + 1);
        return ;
    }
    for (int i = p + 1; i <= q - 1; i++) add[i] += v;
    for (int i = l; i <= R[p]; i++) a[i] += v;
    for (int i = L[q]; i <= r; i++) a[i] += v;
    memmove(rnk + L[p], a + L[p], sizeof(int) * (R[p] - L[p] + 1));
    memmove(rnk + L[q], a + L[q], sizeof(int) * (R[q] - L[q] + 1));
    sort(rnk + L[p], rnk + R[p] + 1), sort(rnk + L[q], rnk + R[q] + 1);
}
int qry(int l, int r, int v) {
    int ret = 0, p = pos[l], q = pos[r];
    if (p == q) {
        for (int i = l; i <= r; i++) ret += ((a[i] + add[pos[i]]) < v);
        return ret;
    }
    for (int i = p + 1; i <= q - 1; i++) {
        ret += lower_bound(rnk + L[i], rnk + R[i] + 1, v - add[i]) - (rnk + L[i] - 1) - 1;
    }
    for (int i = l; i <= R[p]; i++) ret += ((a[i] + add[p]) < v);
    for (int i = L[q]; i <= r; i++) ret += ((a[i] + add[q]) < v);
    return ret;
}
int main(void) {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", a + i);
    init();
    for (int i = 1, op, l, r, c; i <= n; i++) {
        scanf("%d%d%d%d", &op, &l, &r, &c);
        if (op == 0) {
            upd(l, r, c);
        } else {
            printf("%d\n", qry(l, r, c * c));
        }
    }
    return 0;
}

LOJ 数列分块入门 3

区间加法，查区间前驱。

和前一道题一样，我们进行块内排序。

查询的时候 lower_bound 完以后，往回数一个就好了。

零散的还是一个个找。

时间复杂度 \(O(N\sqrt N \log N)\)。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5 + 5;
int len = 300, n, a[N], cnt;
int pos[N], add[N], L[N], R[N], rnk[N];
void init() {
    for (int i = 1; i <= n; i++) pos[i] = (i - 1) / len + 1;
    cnt = pos[n];
    for (int i = 1; i <= cnt; i++) L[i] = (i - 1) * len + 1, R[i] = min(n, i * len);
    memmove(rnk, a, sizeof(int) * n);
    for (int i = 1; i <= cnt; i++) sort(rnk + L[i], rnk + R[i] + 1);
}
void upd(int l, int r, int v) {
    int p = pos[l], q = pos[r];
    if (p == q) {
        for (int i = l; i <= r; i++) a[i] += v;
        memmove(rnk + L[p], a + L[p], sizeof(int) * (R[p] - L[p] + 1));
        sort(rnk + L[p], rnk + R[q] + 1);
        return ;
    }
    for (int i = p + 1; i <= q - 1; i++) add[i] += v;
    for (int i = l; i <= R[p]; i++) a[i] += v;
    for (int i = L[q]; i <= r; i++) a[i] += v;
    memmove(rnk + L[p], a + L[p], sizeof(int) * (R[p] - L[p] + 1));
    memmove(rnk + L[q], a + L[q], sizeof(int) * (R[q] - L[q] + 1));
    sort(rnk + L[p], rnk + R[p] + 1), sort(rnk + L[q], rnk + R[q] + 1);
}
int qry(int l, int r, int v) {
    int ret = -1, p = pos[l], q = pos[r];
    if (p == q) {
        for (int i = l; i <= r; i++) {
            if ((a[i] + add[p]) < v) {
                ret = max(ret, a[i] + add[p]);
            }
        }
        return ret;
    }
    for (int i = p + 1; i <= q - 1; i++) {
        int rkv = lower_bound(rnk + L[i], rnk + R[i] + 1, v - add[i]) - rnk;
        if (rkv != L[i]) ret = max(ret, rnk[rkv - 1] + add[i]);
    }
    for (int i = l; i <= R[p]; i++)
        if (a[i] + add[p] < v) ret = max(ret, a[i] + add[p]);
    for (int i = L[q]; i <= r; i++) 
        if (a[i] + add[q] < v) ret = max(ret, a[i] + add[q]);
    return ret;
}
int main(void) {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", a + i);
    init();
    for (int i = 1, op, l, r, c; i <= n; i++) {
        scanf("%d%d%d%d", &op, &l, &r, &c);
        if (op == 0) {
            upd(l, r, c);
        } else {
            printf("%d\n", qry(l, r, c));
        }
    }
    return 0;
}

LOJ 数列分块入门 4

经典的区间加，区间求和。

维护块内数的和、整体的增量，一个一个加的时候就直接加到和里面，整块的时候加到增量里面。

最后所求的和就是维护的和 + 本块块长 * 区间增量。

和线段树很类似。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 5e4 + 5;
int len = 250, n, a[N], cnt;
int pos[N], L[N], R[N];
ll add[N], sum[N];
void init() {
    for (int i = 1; i <= n; i++) pos[i] = (i - 1) / len + 1;
    for (int i = 1; i <= n; i++) sum[pos[i]] += a[i];
    cnt = pos[n];
    for (int i = 1; i <= cnt; i++) L[i] = (i - 1) * len + 1, R[i] = min(n, i * len);
}
void upd(int l, int r, int v) {
    int p = pos[l], q = pos[r];
    if (p == q) {
        for (int i = l; i <= r; i++) a[i] += v, sum[p] += v;
        return ;
    }
    for (int i = p + 1; i <= q - 1; i++) add[i] += v;
    for (int i = l; i <= R[p]; i++) a[i] += v, sum[p] += v;
    for (int i = L[q]; i <= r; i++) a[i] += v, sum[q] += v;
}
int qry(int l, int r, int mod) {
    int p = pos[l], q = pos[r];
    ll ret = 0;
    if (p == q) {
        for (int i = l; i <= r; i++) {
            ret = (ret + a[i] + add[p]) % mod;
        }
        return ret;
    }
    for (int i = p + 1; i <= q - 1; i++) {
        ret = (ret + sum[i] + add[i] * (R[i] - L[i] + 1) % mod) % mod;
    }
    for (int i = l; i <= R[p]; i++)
        ret = (ret + a[i] + add[p]) % mod;
    for (int i = L[q]; i <= r; i++) 
        ret = (ret + a[i] + add[q]) % mod;
    return ret;
}
int main(void) {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", a + i);
    init();
    for (int i = 1, op, l, r, c; i <= n; i++) {
        scanf("%d%d%d%d", &op, &l, &r, &c);
        if (op == 0) {
            upd(l, r, c);
        } else {
            printf("%d\n", qry(l, r, c + 1));
        }
    }
    return 0;
}

块状链表

咕。

轻重链剖分（树剖）

咕。

标签：入门,分块,int,void,pos,include,快速
From： https://www.cnblogs.com/Lewis-Li/p/decompose.html

分块快速入门