img

分块

分块算法实质上是一种是通过分成多块后在每块上打标记以实现快速区间修改，区间查询的一种算法。其均摊时间复杂度为 O(\(\sqrt{n}\))

分块算法相较于各种树形数据结构，具有简便易写，方便调试等多种优点。在同等数据规模下，如 1e5 ，其时间效率并不会低太多，在考试时反而是一种有力的得分方法。

为了使得其有着最稳定的时间复杂度，我们经常讲一个长度为 n 的序列分为 \(\sqrt{n}\) 个大小为 \(\sqrt{n}\) 的块，如果 n 不是完全平方数，则序列最右端会多出一个角块

长度为 10 的序列被分为了 4 块，前三块的大小为 10 的近似值 3 ，最后一个角块大小为 1

image-20240314093835811

而我们要记录的一个值，就是每个序号代表的数，属于哪一块

1,2,3 就属于第一块， 4,5,6 就属于第二块， 7,8,9 就属于第三块， 10 就属于第四块

可以得到获取每一个序号的所在块的代码是：

1
2
3
4
5
6
int n;//总个数
int block=sqrt(n);//每一块大小
for(int i=1;i<=n;i++)
{
    belong[i]=(i-1)/block+1;//每一个数所在块
}

其他预处理：

1
2
3
4
5
6
int sq = sqrt(n);
for (int i = 1; i <= sq; ++i)
{
    st[i] = n / sq * (i - 1) + 1; // st[i]表示i号块的第一个元素的下标
    ed[i] = n / sq * i; // ed[i]表示i号块的最后一个元素的下标
}

有时候需要

1
ed[sq] = n;

然后，我们为每个元素确定它所归属的块：

1
2
3
for (int i = 1; i <= sq; ++i)
    for (int j = st[i]; j <= ed[i]; ++j)
        bel[j] = i; // 表示j号元素归属于i块

预处理每个块的大小：

1
2
for (int i = 1; i <= sq; ++i)
    size[i] = ed[i] - st[i] + 1;

读入和预处理数据

1
2
3
4
5
for (int i = 1; i <= n; ++i)
    cin>>A[i];
for (int i = 1; i <= sq; ++i)
    for (int j = st[i]; j <= ed[i]; ++j)
        sum[i] += A[j];

sum[i]保存第i个块的和。

区间修改

首先是区间修改，当x与y在同一块内时，直接暴力修改原数组和sum数组：

1
2
3
4
5
6
if (bel[x] == bel[y])
    for (int i = x; i <= y; ++i)
    {
        A[i] += k;
        sum[bel[i]] += k;
    }

否则，先暴力修改左右两边的零散区间：

1
2
3
4
5
6
7
8
9
10
for (int i = x; i <= ed[bel[x]]; ++i)
{
    A[i] += k;
    sum[bel[i]] += k;
}
for (int i = st[bel[y]]; i <= y; ++i)
{
    A[i] += k;
    sum[bel[i]] += k;
}

然后对中间的整块打上标记：

1
2
for (int i = bel[x] + 1; i < bel[y]; ++i)
    mark[i] += k;

区间查询

同样地，如果左右两边在同一块，直接暴力计算区间和。

1
2
3
if (bel[x] == bel[y])
    for (int i = x; i <= y; ++i)
        s += A[i] + mark[bel[i]]; // 注意要加上标记

否则，暴力计算零碎块：

1
2
3
4
for (int i = x; i <= ed[bel[x]]; ++i)
    s += A[i] + mark[bel[i]];
for (int i = st[bel[y]]; i <= y; ++i)
    s += A[i] + mark[bel[i]];

再处理整块：

1
2
for (int i = bel[x] + 1; i < bel[y]; ++i)
    s += sum[i] + mark[i] * size[i]; // 注意标记要乘上块长

于是就可以A出线段树的模板题目了

真是十分暴力啊。

教主的魔法

题目描述

教主最近学会了一种神奇的魔法，能够使人长高。于是他准备演示给 XMYZ 信息组每个英雄看。于是 \(N\) 个英雄们又一次聚集在了一起，这次他们排成了一列，被编号为 \(1, 2, \ldots, N\)。

每个人的身高一开始都是不超过 \(1000\) 的正整数。教主的魔法每次可以把闭区间 \([L, R]\)（\(1≤L≤R≤N\)）内的英雄的身高全部加上一个整数 \(W\)。（虽然 \(L=R\) 时并不符合区间的书写规范，但我们可以认为是单独增加第 \(L(R)\) 个英雄的身高）

CYZ、光哥和 ZJQ 等人不信教主的邪，于是他们有时候会问 WD 闭区间 \([L, R]\) 内有多少英雄身高大于等于 \(C\)，以验证教主的魔法是否真的有效。

WD 巨懒，于是他把这个回答的任务交给了你。

输入格式

第 \(1\) 行为两个整数 \(N, Q\)。\(Q\) 为问题数与教主的施法数总和。

第 \(2\) 行有 \(N\) 个正整数，第 \(i\) 个数代表第 \(i\) 个英雄的身高。

第 \(3\) 到第 \(Q+2\) 行每行有一个操作：

  1. 若第一个字母为 M，则紧接着有三个数字 \(L, R, W\)。表示对闭区间 \([L, R]\) 内所有英雄的身高加上 \(W\)。

  2. 若第一个字母为 A，则紧接着有三个数字 \(L, R, C\)。询问闭区间 \([L, R]\) 内有多少英雄的身高大于等于 \(C\)。

输出格式

对每个 A 询问输出一行，仅含一个整数，表示闭区间 \([L, R]\) 内身高大于等于 \(C\) 的英雄数。

样例 #1

样例输入 #1

1
2
3
4
5
5 3
1 2 3 4 5
A 1 5 4
M 3 5 1
A 1 5 4

样例输出 #1

1
2
2
3

提示

【输入输出样例说明】

原先 \(5\) 个英雄身高为 \(1, 2, 3, 4, 5\)，此时 \([1, 5]\) 间有 \(2\) 个英雄的身高大于等于 \(4\)。教主施法后变为 \(1, 2, 4, 5, 6\)，此时 \([1, 5]\) 间有 \(3\) 个英雄的身高大于等于 \(4\)。

【数据范围】

对于 \(30\%\) 的数据，\(N≤1000\)，\(Q≤1000\)。

对于 \(100\%\) 的数据，\(N≤10^6\)，\(Q≤3000\)，\(1≤W≤1000\)，\(1≤C≤10^9\)。

\(\text{upd 2022.8.18}\)：新增加一组 Hack 数据。
\(\text{upd 2023.8.16}\)：新增加一组 Hack 数据。

区间加用分块很方便

但区间查却比较麻烦

因此可以考虑进行二分

但是有一个点需要注意

对零碎快单独修改后要更新排序后的数组

还能接受吧

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1000005, SQ = 1005;
int st[SQ], ed[SQ], sze[SQ], bel[MAXN];
void init_block(int n) // 初始化
{
    int sq = sqrt(n);
    for (int i = 1; i <= sq; ++i)
    {
        st[i] = n / sq * (i - 1) + 1;
        ed[i] = n / sq * i;
    }
    ed[sq] = n;
    for (int i = 1; i <= sq; ++i)
        for (int j = st[i]; j <= ed[i]; ++j)
            bel[j] = i;
    for (int i = 1; i <= sq; ++i)
        sze[i] = ed[i] - st[i] + 1;
}
int A[MAXN], mark[SQ];
vector<int> v[SQ]; // 这里用vector存排序后的数组
void update(int b) // 更新排序后的数组
{
    for (int i = 0; i <= sze[b]; ++i)
        v[b][i] = A[st[b] + i];
    sort(v[b].begin(), v[b].end());
}
int main()
{
    int n , m ;
    cin>>n>>m;
    int sq = sqrt(n);
    init_block(n);
    for (int i = 1; i <= n; ++i)
        cin>>A[i];
    for (int i = 1; i <= sq; ++i)
        for (int j = st[i]; j <= ed[i]; ++j)
            v[i].push_back(A[j]);
    //每个块的数字都放进去
    for (int i = 1; i <= sq; ++i)
        sort(v[i].begin(), v[i].end());
    //每个块都进行排序
    while (m--)
    {
        char o;
        cin>>o;
        int l  ,r , k ;
        cin>>l>>r>>k;
        if (o == 'M')
        {
            if (bel[l] == bel[r]) // 如果同属一块直接暴力
            {
                for (int i = l; i <= r; ++i)
                    A[i] += k;
                update(bel[l]);
                continue;
            }
            for (int i = l; i <= ed[bel[l]]; ++i) // 对零散块暴力处理
                A[i] += k;
            for (int i = st[bel[r]]; i <= r; ++i)
                A[i] += k;
            update(bel[l]);
            update(bel[r]);
            for (int i = bel[l] + 1; i < bel[r]; ++i) // 打上标记
                mark[i] += k;
        }
        else
        {
            int tot = 0;
            if (bel[l] == bel[r])
            {
                for (int i = l; i <= r; ++i)
                    if (A[i] + mark[bel[l]] >= k)
                        tot++;
                cout<<tot<<'\n';
                continue;
            }
            for (int i = l; i <= ed[bel[l]]; ++i)
                if (A[i] + mark[bel[l]] >= k)
                    tot++;
            for (int i = st[bel[r]]; i <= r; ++i)
                if (A[i] + mark[bel[r]] >= k)
                    tot++;
            // 二分查找k-mark[i]的位置，因为整块都加上了mark[i]其实就相当于k减去mark[i]
            for (int i = bel[l] + 1; i < bel[r]; ++i) 
                tot += v[i].end() - lower_bound(v[i].begin(), v[i].end(), k - mark[i]);
          cout<<tot<<'\n';
        }
    }
    return 0;
}