[学习笔记] 分块

oi

我的第一发高级数据结构qwq

分块比线段树块,夭寿啦…
理论复杂度O(nsqrt(n))
还行了…

代码如下

变量意义:

  • n: 输入的数字数量
  • m: 输入的指令数量
  • op: 题中条件,给的1,2
  • x, y, z: 题中条件,修改的范围和区间加的值
  • block_size: 每一个块的大小,在init函数里计算
  • block_num: 块的个数,准确初始化
  • 结构体valll: 每一个数字的结构体
  • valll里的belong表示该数字属于哪一个块,以后会很方便
  • valll里的val表示当前数字
  • 结构体block: 表示一个块
  • l, r表示管理的闭区间
  • this_sum表示本块的数字总和
    t_sum表示块里总体加的数字,防止暴力过多 这里表示的是总体,我把和拆开拆成块里的数字和这个t_sum来表示,有点lazytag的感觉,只是在求和的之后别忘了加上这个t_sum * (l - r + 1)

代码中的pair基本都是表示一个区间,我懒得写struct了qwq

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
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
/*
* by kriaeth
* status: AC
*/
#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
namespace solve
{
template<typename T>
inline T min(T a, T b)
{
return a < b ? a : b;
}

template<typename T>
inline T max(T a, T b)
{
return a < b ? b : a;
}

inline char read()
{
static const int IN_LEN = 1000000;
static char buf[IN_LEN], *s, *t;
s == t ? t = (s = buf) + fread(buf, 1, IN_LEN, stdin) : 0;
return s == t ? -1 : *s++;
}

template <typename T>
inline void read(T &x)
{
static char c;
static bool iosig;
for (c = read(), iosig = false; !isdigit(c); c = read())
{
if (c == -1) return;
c == '-' ? iosig = true : 0;
}
for (x = 0; isdigit(c); c = read()) x = (x + (x << 2) << 1) + (c ^ '0');
iosig ? x = -x : 0;
}

// 此前全都是读入优化
// 变量定义
const int maxn = 100005;

int n, m, block_num;
int op, x, y, k;
int block_size;
//-----------
struct valll
{
int belong, val;

valll(): belong(0), val(0) {}
};

valll vals[maxn]; // 下标统一从1开始

struct block
{
int l, r;
int this_sum;
int t_sum;
block(): l(0), r(0), this_sum(0), t_sum(0) {}

inline pair<int, int> get_range(int ql, int qr)
{
static pair<int, int> ret;
if(ql >= l)
{
if(ql <= r)
ret.first = ql;
else ret.first = 0;
}
else ret.first = l;

if(qr <= r)
{
if(qr >= l)
ret.second = qr;
else ret.second = 0;
}
else ret.second = r;
return ret;
}

inline void init_this_sum()
{
this_sum = 0;
for (int i = l; i <= r; ++i)
this_sum += vals[i].val;
}

inline long long get_sum(int ql, int qr)
{
pair<int, int> qwq = get_range(ql, qr);
if(qwq.first == l && qwq.second == r) return this_sum;
long long summ = 0;
for (int i = qwq.first; i <= qwq.second; ++i) summ += vals[i].val;
// cout << t_sum << endl;
summ += (t_sum * (qwq.second - qwq.first + 1));
return summ;
}

inline void modify_range(int ql, int qr, int k)
{
// 如果是包含的话..直接全加,如果不是包含的话,就加一半
auto t = get_range(ql, qr);
if(t.first == l && t.second == r) t_sum += k;
else for (int i = t.first; i <= t.second; ++i) vals[i].val += k;
this_sum += ((t.second - t.first + 1) * k);
// lazy_tag.push(pair<pair<int, int>, int>(get_range(ql, qr), k));
}
};
//-----------
block *blocks;

inline void init()
{
read(n); read(m);
block_size = int(sqrt(n));
for (register int i = 1; i <= n; ++i) read(vals[i].val);
// 初始化需要的块的个数...并初始化块本身, 利用动态数组
block_num = n % block_size == 0 ? n / block_size : n / block_size + 1;
blocks = new block[block_num + 5];
// 初始化blocks的左右端点
int curr = 1;
for (int i = 1 ; i <= block_num; ++i)
blocks[i].l = curr, blocks[i].r = (curr += block_size) - 1;
blocks[block_num].r = n;
// 遍历认领val属于的blocks 并且初始化blocks内部的前缀和数组和sum数组
for (int i = 1; i <= block_num; ++i)
{
for (int j = blocks[i].l; j <= blocks[i].r; ++j)
vals[j].belong = i;
blocks[i].init_this_sum();
}
}

inline void modify_range(int ql, int qr, int k)
{
for (int i = vals[ql].belong; i <= vals[qr].belong; ++i)
blocks[i].modify_range(ql, qr, k);
}

inline long long get_sum(int ql, int qr)
{
long long summ = 0;
for (int i = vals[ql].belong; i <= vals[qr].belong; ++i)
summ += blocks[i].get_sum(ql, qr);
return summ;
}
inline void solve()
{
init();
for (int i = 0; i < m; ++i)
{
read(op); read(x); read(y);
if(op == 1)
{
read(k);
modify_range(x, y, k);
}
if(op == 2)
std::printf("%lld\n", get_sum(x, y));
}

}
}

int main()
{
solve::solve();
return 0;
}

请忽略超长的模板代码
核心大概就那点了…我把分离出来

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
inline void init()
{
read(n); read(m);
block_size = int(sqrt(n));
for (register int i = 1; i <= n; ++i) read(vals[i].val);
// 初始化需要的块的个数...并初始化块本身, 利用动态数组
block_num = n % block_size == 0 ? n / block_size : n / block_size + 1;
blocks = new block[block_num + 5];
// 初始化blocks的左右端点
int curr = 1;
for (int i = 1 ; i <= block_num; ++i)
blocks[i].l = curr, blocks[i].r = (curr += block_size) - 1;
blocks[block_num].r = n;
// 遍历认领val属于的blocks 并且初始化blocks内部的前缀和数组和sum数组
for (int i = 1; i <= block_num; ++i)
{
for (int j = blocks[i].l; j <= blocks[i].r; ++j)
vals[j].belong = i;
blocks[i].init_this_sum();
}
}

这里是建立块的代码,自己打一次基本上就懂了…
首先读入,然后用
for (int i = 1 ; i <= block_num; ++i) blocks[i].l = curr, blocks[i].r = (curr += block_size) - 1;来初始化每一个块的左右端点…
再用一个for (int i = 1; i <= block_num; ++i){ for (int j = blocks[i].l; j <= blocks[i].r; ++j) vals[j].belong = i; blocks[i].init_this_sum();}来初始化每一个块和每一个数字对应的块
后面是块的应用的关键…稍微不小心就会想成暴力(当然是脑补的情况)(比如说我

为了方便计算,我加了这样一个函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
inline pair<int, int> get_range(int ql, int qr)
{
static pair<int, int> ret;
if(ql >= l)
{
if(ql <= r)
ret.first = ql;
else ret.first = 0;
}
else ret.first = l;

if(qr <= r)
{
if(qr >= l)
ret.second = qr;
else ret.second = 0;
}
else ret.second = r;
return ret;
}

忽略这么丑的这一段…看一下作用
就是求总段落与当前块的交集

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
inline long long get_sum(int ql, int qr)
{
pair<int, int> qwq = get_range(ql, qr);
if(qwq.first == l && qwq.second == r) return this_sum;
long long summ = 0;
for (int i = qwq.first; i <= qwq.second; ++i) summ += vals[i].val;
// cout << t_sum << endl;
summ += (t_sum * (qwq.second - qwq.first + 1));
return summ;
}
inline void modify_range(int ql, int qr, int k)
{
// 如果是包含的话..直接全加,如果不是包含的话,就加一半
auto t = get_range(ql, qr);
if(t.first == l && t.second == r) t_sum += k;
else for (int i = t.first; i <= t.second; ++i) vals[i].val += k;
this_sum += ((t.second - t.first + 1) * k);
// lazy_tag.push(pair<pair<int, int>, int>(get_range(ql, qr), k));
}

第一个是获取当前块内的和
如果是求这个整块的话,直接求和
如果是求一部分的话,暴力求解,然后加上t_sum,因为块里的每一个元素都被加上过这个t_sum,但是本身没有算

第二个是修改区间
还是那样,如果是整区间,那就只加t_sum
如果不是整区间,那就分开暴力加,别忘了加总和的this_sum

~