「分块九题定律」分块!

「分块九题定律」分块!

根据HZW学长的博客 分块 的内容,趁这机会把分块补了,好为接下来的莫队做准备QAQQ

分块 : 优美的暴力(虽然我并不知道这个优美的评定是怎么评价的)
学习理由 : 不会线段树
学习方式 : 直接啃代码.. 没什么好说的 暴力修改 + 区间标记 我想大家都知道该怎么写
小白学习方式 :

  • 不要直接看代码 不要直接看代码 不要直接看代码 (重要的事情说三遍)
  • 先了解以下几个概念
    • 分块就是将长度为 N 的数列分成 $\sqrt{x}$ 个长度为 $\sqrt{x}$ 的小区间
    • 对于一段序列,如果里面的数不满 $\sqrt{x}$ 个,那么就暴力修改,否则给小区间打上标记,表示这个小区间内的所有值都需要更改
    • 可以穿插任何操作.. (甚至可以用 数据结构 维护 (暴力出奇迹)
    • 更多的细节,需要自己实践 或者 看下方代码

第一题

给出一个长为n的数列,以及n个操作,操作涉及区间加法,单点查值

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
 //#define fre yes

#include <cmath>
#include <cstdio>
#include <iostream>

const int MAXN_INT = 50005;
int belong[MAXN_INT], l[MAXN_INT], r[MAXN_INT], Lazy[MAXN_INT], arr[MAXN_INT];

int num, black;

template<typename T>inline void read(T&x) {
x = 0; char c; int lenp = 1;
do { c = getchar(); if(c == '-') lenp = -1; } while(!std::isdigit(c));
do { x = x * 10 + c - '0'; c = getchar(); } while(std::isdigit(c));
x *= lenp;
}

void build(int n) {
black = sqrt(n);
num = n / black;
if(n % black) num++;

for (int i = 1; i <= num; i++) {
l[i] = (i - 1) * black + 1, r[i] = i * black;
} r[num] = n;
for (int i = 1; i <= n; i++) {
belong[i] = (i - 1) / black + 1;
}
}

void update(int x, int y, int val) {
if(belong[x] == belong[y]) {
for (int i = x; i <= y; i++) {
arr[i] += val;
}
}

if(belong[x] != belong[y]) {
for (int i = x; i <= r[belong[x]]; i++) {
arr[i] += val;
}
for (int i = belong[x] + 1; i <= belong[y] - 1; i++) {
Lazy[i] += val;
}
for (int i = l[belong[y]]; i <= y; i++) {
arr[i] += val;
}
}
}

int main() {
static int n;
read(n);
for (int i = 1; i <= n; i++) {
read(arr[i]);
}

build(n);

for (int i = 1; i <= n; i++) {
int opt, le, re, c;
read(opt); read(le); read(re); read(c);
if(opt == 0) {
update(le, re, c);
} if(opt == 1) {
printf("%d\n", arr[re] + Lazy[belong[re]]);
}
} return 0;
}

第二题

给出一个长为n的数列,以及n个操作,操作涉及区间加法,询问区间内小于某个值x的元素个数

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
//#define fre yes

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>

const int MAXN_INT = 50005;
int arr[MAXN_INT];
int belong[MAXN_INT], l[MAXN_INT], r[MAXN_INT], Lazy[MAXN_INT];

int block, num, n;

std::vector<int> v[505];

void build() {
block = sqrt(n);
num = n / block;
if(n % block) num++;

for (int i = 1; i <= num; i++) {
l[i] = (i - 1) * block + 1, r[i] = i * block;
} r[num] = n;
for (int i = 1; i <= n; i++) {
belong[i] = (i - 1) / block + 1;
v[belong[i]].push_back(arr[i]);
}

for (int i = 1; i <= num; i ++) {
std::sort(v[i].begin(), v[i].end());
}
}

void update(int x, int y, int val) {
if(belong[x] == belong[y]) {
v[belong[x]].clear();
for (int i = x; i <= y; i++) {
arr[i] += val;
}

for (int i = l[belong[x]]; i <= r[belong[x]]; i++) {
v[belong[x]].push_back(arr[i]);
} sort(v[belong[x]].begin(), v[belong[x]].end());
return ;
}

if(belong[x] != belong[y]) {
v[belong[x]].clear();
for (int i = x; i <= r[belong[x]]; i++) {
arr[i] += val;
}

for (int i = l[belong[x]]; i <= r[belong[x]]; i++) {
v[belong[x]].push_back(arr[i]);
}

sort(v[belong[x]].begin(), v[belong[x]].end());

for (int i = belong[x] + 1; i <= belong[y] - 1; i++) {
Lazy[i] += val;
}

v[belong[y]].clear();
for (int i = l[belong[y]]; i <= y; i++) {
arr[i] += val;
}

for (int i = l[belong[y]]; i <= r[belong[y]]; i++) {
v[belong[y]].push_back(arr[i]);
}

sort(v[belong[y]].begin(), v[belong[y]].end());
}
}

// int binarySearch(int x, int y, int val) {
// int pos;
// while(x < y) {
// int mid = (x + y) >> 1;
// if(arr[mid] < val) {
// x = mid + 1;
// pos = x;
// } else {
// y = mid - 1;
// pos = y;
// }
// }

// return pos;
// }

int query(int x, int y, int val) {
int ans = 0;
if(belong[x] == belong[y]) {
for (int i = x; i <= y; i++) {
if(arr[i] < (val - Lazy[belong[x]])) {
ans++;
}
} return ans;
}

if(belong[x] != belong[y]) {
for (int i = x; i <= r[belong[x]]; i++) {
if(arr[i] < (val - Lazy[belong[x]])) {
ans++;
}
}

std::vector<int>::iterator it;
for (int i = belong[x] + 1; i <= belong[y] - 1; i++) {
it = std::upper_bound(v[i].begin(), v[i].end(), val - Lazy[i] - 1);
if(it == v[i].end()) ans += block;
else ans += it - v[i].begin();
}

for (int i = l[belong[y]]; i <= y; i++) {
if(arr[i] < (val - Lazy[belong[y]])) {
ans++;
}
}
}

return ans;
}

int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", &arr[i]);
}

build();

for (int i = 1; i <= n; i++) {
int opt, el, er, c;
scanf("%d %d %d %d", &opt, &el, &er, &c);
if(opt == 0) {
update(el, er, c);
}
if(opt == 1) {
printf("%d\n", query(el, er, c * c));
}
} return 0;
}

第三题

给出一个长为n的数列,以及n个操作,操作涉及区间加法,询问区间内小于某个值x的前驱(比其小的最大元素)

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
//#define fre yes

#include <cmath>
#include <vector>
#include <cstdio>
#include <iostream>
#include <algorithm>

const int MAXN_INT = 100005;
int arr[MAXN_INT], l[MAXN_INT], r[MAXN_INT], belong[MAXN_INT];
int Lazy[MAXN_INT];

int num, block;

std::vector<int> v[505];

void build(int n) {
block = sqrt(n);
num = n / block;
if(n % block) num++;

for (int i = 1; i <= n; i++) {
belong[i] = ((i - 1) / block) + 1;
}

for (int i = 1; i <= n; i++) {
v[belong[i]].push_back(arr[i]);
}

for (int i = 1; i <= num; i++) {
l[i] = (i - 1) * block + 1, r[i] = i * block;
std::sort(v[i].begin(), v[i].end());
}
}

void update(int x, int y, int val) {
if(belong[x] == belong[y]) {
v[belong[x]].clear();
for (int i = x; i <= y; i++) {
arr[i] += val;
}

for (int i = l[belong[x]]; i <= r[belong[x]]; i++) {
v[belong[x]].push_back(arr[i]);
}

std::sort(v[belong[x]].begin(), v[belong[x]].end());
}

if(belong[x] != belong[y]) {
v[belong[x]].clear();
for (int i = x; i <= r[belong[x]]; i++) {
arr[i] += val;
}

for (int i = l[belong[x]]; i <= r[belong[x]]; i++) {
v[belong[x]].push_back(arr[i]);
}

std::sort(v[belong[x]].begin(), v[belong[x]].end());

for (int i = belong[x] + 1; i <= belong[y] - 1; i++) {
Lazy[i] += val;
}

v[belong[y]].clear();
for (int i = l[belong[y]]; i <= y; i++) {
arr[i] += val;
}

for (int i = l[belong[y]]; i <= r[belong[y]]; i++) {
v[belong[y]].push_back(arr[i]);
}

std::sort(v[belong[y]].begin(), v[belong[y]].end());
}
}

int query(int x, int y, int val) {
int date = -0x3f3f3f;
if(belong[x] == belong[y]) {
for (int i = x; i <= y; i++) {
if(arr[i] + Lazy[belong[x]] < val) {
date = std::max(date, arr[i] + Lazy[belong[x]]);
}
}
}

if(belong[x] != belong[y]) {
for (int i = x; i <= r[belong[x]]; i++) {
if(arr[i] + Lazy[belong[x]] < val) {
date = std::max(date, arr[i] + Lazy[belong[x]]);
}
}

for (int i = l[belong[y]]; i <= y; i++) {
if(arr[i] + Lazy[belong[y]] < val) {
date = std::max(date, arr[i] + Lazy[belong[y]]);
}
}

int u = 0;
for (int i = belong[x] + 1; i <= belong[y] - 1; i++) {
if(v[i].at(0) + Lazy[i] >= val) continue;
u = std::lower_bound(v[i].begin(), v[i].end(), val - Lazy[i]) - v[i].begin();
if(u == 0) continue;
u--;
date = std::max(date, v[i].at(u) + Lazy[i]);
}
} return date;
}

int main() {
static int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", &arr[i]);
}

build(n);

for (int i = 1; i <= n; i++) {
int opt, el, er, c;
scanf("%d %d %d %d", &opt, &el, &er, &c);
if(opt == 0) {
update(el, er, c);
}
if(opt == 1) {
int k = query(el, er, c);
if(k == -0x3f3f3f) puts("-1");
else printf("%d\n", k);
}
} return 0;
}

第四题

给出一个长为n的数列,以及n个操作,操作涉及区间加法,区间求和

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
//#define fre yes

#include <cmath>
#include <cstdio>

const int MAXN_INT = 50005;
long long arr[MAXN_INT], l[MAXN_INT], r[MAXN_INT], belong[MAXN_INT];
long long sum[MAXN_INT], Lazy[MAXN_INT];

int num, block;

void build(int n) {
block = sqrt(n);
num = n / block;
if(n % block) num++;

for (int i = 1; i <= num; i++) {
l[i] = (i - 1) * block + 1, r[i] = i * block;
} r[num] = n;
for (int i = 1; i <= n; i++) {
belong[i] = (i - 1) / block + 1;
}

for (int i = 1; i <= n; i++) {
sum[belong[i]] += arr[i];
}
}

void update(int x, int y, int val) {
if(belong[x] == belong[y]) {
for (int i = x; i <= y; i++) {
arr[i] += val;
sum[belong[x]] += val;
}
}

if(belong[x] != belong[y]) {
for (int i = x; i <= r[belong[x]]; i++) {
arr[i] += val;
sum[belong[x]] += val;
}

for (int i = belong[x] + 1; i <= belong[y] - 1; i++) {
Lazy[i] += val;
}

for (int i = l[belong[y]]; i <= y; i++) {
arr[i] += val;
sum[belong[y]] += val;
}
}
}

long long query(int x, int y) {
long long ans = 0;
if(belong[x] == belong[y]) {
for (int i = x; i <= y; i++) {
ans += arr[i] + Lazy[belong[x]];
}
}

if(belong[x] != belong[y]) {
for (int i = x; i <= r[belong[x]]; i++) {
ans += arr[i] + Lazy[belong[x]];
}

for (int i = l[belong[y]]; i <= y; i++) {
ans += arr[i] + Lazy[belong[y]];
}

for (int i = belong[x] + 1; i <= belong[y] - 1; i++) {
ans += sum[i] + block * Lazy[i];
}
} return ans;
}


int main() {
static int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", &arr[i]);
}

build(n);

for (int i = 1; i <= n; i++) {
int opt, el, er, c;
scanf("%d %d %d %d", &opt, &el, &er, &c);
if(opt == 0) {
update(el, er, c);
}
if(opt == 1) {
printf("%lld\n", query(el, er) % (c + 1));
}
} return 0;
}

第五题

给出一个长为n的数列,以及n个操作,操作涉及区间开方,区间求和

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
//#define fre yes

#include <cmath>
#include <cstdio>

const int MAXN_INT = 50005;
int arr[MAXN_INT], l[MAXN_INT], r[MAXN_INT], belong[MAXN_INT], sum[MAXN_INT];

const int MAXN_BOOL = 50005;
bool Vis[MAXN_BOOL];

int block, num;

void build(int n) {
block = sqrt(n);
num = n / block;
if(n % block) num++;

for (int i = 1; i <= n; i++) {
belong[i] = (i - 1) / block + 1;
}

for (int i = 1; i <= num; i++) {
l[i] = (i - 1) * block + 1, r[i] = i * block;
} r[num] = n;

for (int i = 1; i <= n; i++) {
sum[belong[i]] += arr[i];
}
}

void update(int x, int y) {
if(belong[x] == belong[y]) {
for (int i = x; i <= y; i++) {
sum[belong[x]] -= arr[i];
arr[i] = sqrt(arr[i]);
sum[belong[x]] += arr[i];
}
}

if(belong[x] != belong[y]) {
for (int i = x; i <= r[belong[x]]; i++) {
sum[belong[x]] -= arr[i];
arr[i] = sqrt(arr[i]);
sum[belong[x]] += arr[i];
}

for (int i = l[belong[y]]; i <= y; i++) {
sum[belong[y]] -= arr[i];
arr[i] = sqrt(arr[i]);
sum[belong[y]] += arr[i];
}

for (int i = belong[x] + 1; i <= belong[y] - 1; i++) {
if(Vis[i]) continue;
Vis[i] = 1;
sum[i] = 0;
for (int j = l[i]; j <= r[i]; j++) {
arr[j] = sqrt(arr[j]), sum[i] += arr[j];
if(arr[j] > 1) Vis[i] = 0;
}
}
}
}

int query(int x, int y) {
int ans = 0;
if(belong[x] == belong[y]) {
for (int i = x; i <= y; i++) {
ans += arr[i];
}
}

if(belong[x] != belong[y]) {
for (int i = x; i <= r[belong[x]]; i++) {
ans += arr[i];
}

for (int i = l[belong[y]]; i <= y; i++) {
ans += arr[i];
}

for (int i = belong[x] + 1; i <= belong[y] - 1; i++) {
ans += sum[i];
}
}

return ans;
}

int main() {
static int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", &arr[i]);
} build(n);

for (int i = 1; i <= n; i++) {
int opt, el, er, c;
scanf("%d %d %d %d", &opt, &el, &er, &c);
if(opt == 0) {
update(el, er);
}
if(opt == 1) {
printf("%d\n", query(el, er));
}
} return 0;
}

未完待续…

0%