数列分块入门系列

数列分块入门 1

给出一个长为 $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
#include<bits/stdc++.h>
#define gc getchar
#define ll long long
inline ll read(){ll x = 0; char ch = gc(); bool positive = 1;for (; !isdigit(ch);
ch = gc()) if (ch == '-') positive = 0;for (; isdigit(ch); ch = gc()) x = x * 10
+ ch - '0';return positive ? x : -x;}inline void write(ll a){if(a>=10)write(a/10);
putchar('0'+a%10);}inline void writeln(ll a){if(a<0){a=-a; putchar('-');}write(a);
puts("");}
using namespace std;
const int N = 100010;
int a[N], pos[N], add[N];
int L[N], R[N];
int n, t;
void change(int l, int r, int d) {
int p = pos[l], q = pos[r];
if(p == q) {
for(int i = l; i <= r; ++i)
a[i] += d;
} else {
for(int i = p + 1; i <= q - 1; ++i) add[i] += d;
for(int i = l; i <= R[p]; ++i) a[i] += d;
for(int i = L[q]; i <= r; ++i) a[i] += d;
}
}
int main() {
int opt, l, r, d;
n = read();
for(int i = 1; i <= n; ++i)
a[i] = read();
t = sqrt(n);
for(int i = 1; i <= t; ++i) {
L[i] = (i - 1) * t + 1;
R[i] = i * t;
}
if(R[t] < n) L[++t] = R[t - 1] + 1, R[t] = n;
for(int i = 1; i <= t; ++i)
for(int j = L[i]; j <= R[i]; ++j)
pos[j] = i;
for(int i = 1; i <= n; ++i) {
opt = read(), l = read(), r = read(), d = read();
if(!opt) change(l, r, d);
else writeln(a[r] + add[pos[r]]);
}
return 0;
}

数列分块入门 2

给出一个长为 $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
#include<bits/stdc++.h>
#define gc getchar
#define ll long long
inline ll read(){ll x = 0; char ch = gc(); bool positive = 1;for (; !isdigit(ch);
ch = gc()) if (ch == '-') positive = 0;for (; isdigit(ch); ch = gc()) x = x * 10
+ ch - '0';return positive ? x : -x;}inline void write(ll a){if(a>=10)write(a/10);
putchar('0'+a%10);}inline void writeln(ll a){if(a<0){a=-a; putchar('-');}write(a);
puts("");}
using namespace std;
const int N = 100010;
int n, t;
int a[N], L[N], R[N], pos[N], add[N], b[N];
void change(int l, int r, int d) {
int p = pos[l], q = pos[r];
if(p == q) {
for(int i = l; i <= r; ++i)
a[i] += d;
for(int i = L[p]; i <= R[p]; ++i) b[i] = a[i];
sort(b + L[p], b + R[p] + 1);
}
else {
for(int i = p + 1; i <= q - 1; ++i) add[i] += d;
for(int i = l;i <= R[p]; ++i) a[i] += d;
for(int i = L[q]; i <= r; ++i) a[i] += d;
for(int i = L[p]; i <= R[p]; ++i) b[i] = a[i];
for(int i = L[q]; i <= R[q]; ++i) b[i] = a[i];
sort(b + L[p], b + R[p] + 1);
sort(b + L[q], b + R[q] + 1);
}
}
int find(int l, int r, int x) {
if(b[l] >= x) return l;
int mid;
while(r - l > 1) {
mid = (l + r) >> 1;
if(b[mid] < x) l = mid;
else r = mid;
}
return l + 1;
}
int ask(int l, int r, int v) {
int p = pos[l], q = pos[r], res = 0;
if(p == q)
for(int i = l; i <= r; ++i)
res += a[i] < v - add[p];
else {
for(int i = p + 1; i <= q - 1; ++i)
res += find(L[i], R[i] + 1, v - add[i]) - L[i];
for(int i = l; i <= R[p]; ++i) res += a[i] < v - add[p];
for(int i = L[q]; i <= r; ++i) res += a[i] < v - add[q];
}
return res;
}
int main() {
int opt, l, r, d;
n = read();
for(int i = 1; i <= n; ++i) b[i] = a[i] = read();
t = sqrt(n);
for(int i = 1; i <= t; ++i){
L[i] = (i - 1) * t + 1;
R[i] = i * t;
}
if(R[t] < n)L[++t] = R[t - 1] + 1, R[t] = n;
for(int i = 1; i <= t; ++i) {
sort(b + L[i], b + R[i] + 1);
for(int j = L[i]; j <= R[i]; ++j)
pos[j] = i;
}
for(int i = 1; i <= n; ++i) {
opt = read(), l = read(), r = read(), d = read();
if(!opt) change(l, r, d);
else writeln(ask(l, r, d * d));
}
return 0;
}

数列分块入门 3

给出一个长为 $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
#include<bits/stdc++.h>
#define gc getchar
#define ll long long
inline ll read(){ll x = 0; char ch = gc(); bool positive = 1;for (; !isdigit(ch);
ch = gc()) if (ch == '-') positive = 0;for (; isdigit(ch); ch = gc()) x = x * 10
+ ch - '0';return positive ? x : -x;}inline void write(ll a){if(a>=10)write(a/10);
putchar('0'+a%10);}inline void writeln(ll a){if(a<0){a=-a; putchar('-');}write(a);
puts("");}
using namespace std;
const int N = 100010, inf = 0x3f3f3f3f;
int n, t;
int a[N], L[N], R[N], pos[N], add[N];
set<int>b[N];
void change(int l, int r, int d) {
int p = pos[l], q = pos[r];
if(p == q) {
for(int i = l; i <= r; ++i) a[i] += d;
b[p].clear();
for(int i = L[p]; i <= R[p]; ++i)
b[p].insert(a[i]);
} else {
for(int i = p + 1; i <= q - 1; ++i) add[i] += d;
for(int i = l; i <= R[p]; ++i) a[i] += d;
b[p].clear();
for(int i = L[p]; i <= R[p]; ++i)
b[p].insert(a[i]);
for(int i = L[q]; i <= r; ++i) a[i] += d;
b[q].clear();
for(int i = L[q]; i <= R[q]; ++i)
b[q].insert(a[i]);
}
}
void ask(int l, int r, int v) {
int p = pos[l], q = pos[r];
int ans = -inf;
if(p == q) {
for(int i = l; i <= r; ++i)
if(a[i] + add[p] < v && a[i] + add[q] > ans)
ans = a[i] + add[p];
}
else {
for(int i = p + 1; i <= q - 1; ++i) {
set<int>::iterator it = b[i].lower_bound(v - add[i]);
if(it == b[i].begin()) continue;
--it;
if(ans < *it + add[i]) ans = *it + add[i];
}
for(int i = l; i <= R[p]; ++i)
if(a[i] + add[p]< v && a[i] + add[p] > ans) ans = a[i] + add[p];
for(int i = L[q]; i <= r; ++i)
if(a[i] + add[q]< v && a[i] + add[q] > ans) ans = a[i] + add[q];
}
if(ans == -inf)
puts("-1");
else
writeln(ans);
}
int main() {
int opt, l, r, d;
n = read();
for(int i = 1; i <= n; ++i) a[i] = read();
t = sqrt(n);
for(int i = 1; i <= t; ++i) {
L[i] = (i - 1) * t + 1;
R[i] = i * t;
}
if(R[t] < n) L[++t] = R[t - 1] + 1, R[t] = n;
for(int i = 1; i <= t; ++i)
for(int j = L[i]; j <= R[i]; ++j) {
pos[j] = i;
b[i].insert(a[j]);
}
for(int i = 1; i <= n; ++i) {
opt = read(), l = read(), r = read(), d = read();
if(!opt) change(l, r, d);
else ask(l, r, d);
}
return 0;
}

数列分块入门 4

给出一个长为 $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
#include<bits/stdc++.h>
#define gc getchar
#define ll long long
inline ll read(){ll x = 0; char ch = gc(); bool positive = 1;for (; !isdigit(ch);
ch = gc()) if (ch == '-') positive = 0;for (; isdigit(ch); ch = gc()) x = x * 10
+ ch - '0';return positive ? x : -x;}inline void write(ll a){if(a>=10)write(a/10);
putchar('0'+a%10);}inline void writeln(ll a){if(a<0){a=-a; putchar('-');}write(a);
puts("");}
using namespace std;
const int N = 100010;
ll a[N], sum[N], add[N];
int L[N], R[N];
int pos[N];
int n, m, t;
void change(int l, int r, ll d) {
int p = pos[l], q = pos[r];
if(p == q) {
for(int i = l; i <= r; ++i) a[i] += d;
sum[p] += d * (r - l + 1);
} else {
for(int i = p + 1; i <= q - 1; ++i) add[i] += d;
for(int i = l; i <= R[p]; ++i) a[i] += d;
sum[p] += d * (R[p] - l + 1);
for(int i = L[q]; i <= r; ++i) a[i] += d;
sum[q] += d * (r - L[q] + 1);
}
}
ll ask(int l, int r) {
int p = pos[l], q = pos[r];
ll ans = 0;
if(p == q) {
for(int i = l; i <= r; ++i) ans += a[i];
ans += add[p] * (r - l + 1);
} else {
for(int i = p + 1; i <= q - 1; ++i)
ans += sum[i] + add[i] * (R[i] - L[i] + 1);
for(int i = l; i <= R[p]; ++i) ans += a[i];
ans += add[p] * (R[p] - l + 1);
for(int i = L[q]; i <= r; ++i) ans += a[i];
ans += add[q] * (r - L[q] + 1);
}
return ans;
}
int main() {
int opt, l, r, d;
n = read();
for(int i = 1; i <= n; ++i) a[i] = read();
t = sqrt(n);
for(int i = 1; i <= t; ++i) {
L[i] = (i - 1) * sqrt(n) + 1;
R[i] = i * sqrt(n);
}
if(R[t] < n)L[++t] = R[t - 1] + 1, R[t] = n;
for(int i = 1; i <= t; ++i)
for(int j = L[i]; j <= R[i]; ++j) {
pos[j] = i;
sum[i] += a[j];
}
for(int i = 1; i <= n; ++i) {
opt = read(), l = read(), r = read(), d = read();
if(!opt) change(l, r, d);
else writeln(ask(l, r) % (d + 1));
}
return 0;
}

数列分块入门 5

给出一个长为 $n$ 的数列 $a_1\ldots a_​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
#include<bits/stdc++.h>
#define gc getchar
#define ll long long
inline ll read(){ll x = 0; char ch = gc(); bool positive = 1;for (; !isdigit(ch);
ch = gc()) if (ch == '-') positive = 0;for (; isdigit(ch); ch = gc()) x = x * 10
+ ch - '0';return positive ? x : -x;}inline void write(ll a){if(a>=10)write(a/10);
putchar('0'+a%10);}inline void writeln(ll a){if(a<0){a=-a; putchar('-');}write(a);
puts("");}
using namespace std;
const int N = 100010, inf = 0x3f3f3f3f;
int n, t, L[N], R[N];
int a[N], sum[N], pos[N];
bool flag[N];
void change(int l, int r) {
int p = pos[l], q = pos[r];
if(p == q) {
for(int i = l; i <= r; ++i)
if(a[i] > 1) {
sum[p] -= a[i];
a[i] =sqrt(a[i]);
sum[p] += a[i];
}
} else {
for(int i = p + 1; i <= q - 1; ++i)
if(!flag[i]) {
flag[i] = true;
for(int j = L[i]; j <= R[i]; ++j)
if(a[j] > 1) {
sum[i] -= a[j];
a[j] = sqrt(a[j]);
sum[i] += a[j];
if(a[j] > 1) flag[i] = false;
}
}
for(int i = l; i <= R[p]; ++i)
if(a[i] > 1) {
sum[p] -= a[i];
a[i] = sqrt(a[i]);
sum[p] += a[i];
}
for(int i = L[q]; i <= r; ++i)
if(a[i] > 1) {
sum[q] -= a[i];
a[i] =sqrt(a[i]);
sum[q] += a[i];
}
}
}
int ask(int l, int r) {
int p = pos[l], q = pos[r], res = 0;
if(p == q)
for(int i = l; i <= r; ++i)
res += a[i];
else {
for(int i = p + 1; i <= q - 1; ++i)
res += sum[i];
for(int i = l; i <= R[p]; ++i)
res += a[i];
for(int i = L[q]; i <= r; ++i)
res += a[i];
}
return res;
}
int main() {
int opt, l, r, d;
n = read();
for(int i = 1; i <= n; ++i)
a[i] = read();
t = sqrt(n);
for(int i = 1; i <= t; ++i) {
L[i] = (i - 1) * t + 1;
R[i] = i * t;
}
if(R[t] < n) L[++t] = R[t - 1] + 1, R[t] = n;
for(int i = 1; i <= t; ++i)
for(int j = L[i]; j <= R[i]; ++j) {
pos[j] = i;
sum[i] += a[j];
}
for(int i = 1; i <= n; ++i) {
opt = read(), l = read(), r = read(), d = read();
if(!opt) change(l, r);
else writeln(ask(l, r));
}
return 0;
}

数列分块入门 6

给出一个长为 $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
#include<bits/stdc++.h>
#define gc getchar
#define ll long long
inline ll read(){ll x = 0; char ch = gc(); bool positive = 1;for (; !isdigit(ch);
ch = gc()) if (ch == '-') positive = 0;for (; isdigit(ch); ch = gc()) x = x * 10
+ ch - '0';return positive ? x : -x;}inline void write(ll a){if(a>=10)write(a/10);
putchar('0'+a%10);}inline void writeln(ll a){if(a<0){a=-a; putchar('-');}write(a);
puts("");}
using namespace std;
const int N = 200010;
typedef pair<int, int> PPI;
int n,a[N], m, t;
vector<int>b[N];

PPI ask(int x) {
int y = 1;
while(b[y].size() < x)
x -= b[y].size(), ++y;
return make_pair(y, x - 1);
}
void rebuild() {
n = 0;
for(int i = 1; i <= m; ++i) {
for(vector<int>::iterator j = b[i].begin(); j != b[i].end(); ++j)
a[++n] = *j;
b[i].clear();
}
t = sqrt(n);
for(int i = 1; i <= n; ++i)
b[(i - 1) / t + 1].push_back(a[i]);
m = (n - 1) / t + 1;
}
void change(int x, int v) {
PPI res = ask(x);
b[res.first].insert(b[res.first].begin() + res.second, v);
if(b[res.first].size() >t * 20)
rebuild();
}
int main() {
int opt, l, r, d;
n = read();
for(int i = 1; i <= n; ++i) a[i] = read();
t = sqrt(n);
m = (n - 1) / t + 1;
for(int i = 1; i <= n; ++i)
b[(i - 1) / t + 1].push_back(a[i]);
for(int i = n; i >= 1; --i) {
opt = read(), l = read(), r = read(), d = read();
if(!opt) change(l, r);
else {
PPI ans = ask(r);
writeln(b[ans.first][ans.second]);
}
}
return 0;
}

数列分块入门 7

给出一个长为 $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
#include<bits/stdc++.h>
#define gc getchar
#define ll long long
inline ll read(){ll x = 0; char ch = gc(); bool positive = 1;for (; !isdigit(ch);
ch = gc()) if (ch == '-') positive = 0;for (; isdigit(ch); ch = gc()) x = x * 10
+ ch - '0';return positive ? x : -x;}inline void write(ll a){if(a>=10)write(a/10);
putchar('0'+a%10);}inline void writeln(ll a){if(a<0){a=-a; putchar('-');}write(a);
puts("");}
using namespace std;
const int N = 100010, mod = 10007;
int a[N], n, add[N], mul[N];
int pos[N], L[N], R[N], t;
void reset(int x) {
for(int i = L[x]; i <= R[x]; ++i)
a[i] = (a[i] * mul[x] + add[x]) % mod;
mul[x] = 1, add[x] = 0;
}
void change_add(int l, int r, int d) {
int p = pos[l], q = pos[r];
if(p == q) {
reset(p);
for(int i = l; i <= r; ++i) a[i] = (a[i] + d) % mod;
}
else {
reset(p);
reset(q);
for(int i = p + 1; i <= q - 1; ++i) add[i] = (add[i] + d) % mod;
for(int i = l; i <= R[p]; ++i) a[i] = (a[i] + d) % mod;
for(int i = L[q]; i <= r; ++i) a[i] = (a[i] + d) % mod;
}
}
void change_mul(int l, int r, int d) {
int p = pos[l], q = pos[r];
if(p == q) {
reset(p);
for(int i = l; i <= r; ++i) a[i] = a[i] * d % mod;
}
else {
reset(p);
reset(q);
for(int i = p + 1; i <= q - 1; ++i) {
add[i] = (add[i] * d) % mod;
mul[i] = (mul[i] * d) % mod;
}
for(int i = l; i <= R[p]; ++i) a[i] = a[i] * d % mod;
for(int i = L[q]; i <= r; ++i) a[i] = a[i] * d % mod;
}

}
int main() {
int opt, l, r, d;
n = read();
for(int i = 1; i <= n; ++i) a[i] = read();
t = sqrt(n);
for(int i = 1; i <= t; ++i) {
L[i] = (i - 1) * t + 1;
R[i] = i * t;
}
if(R[t] < n) L[++t] = R[t - 1] + 1, R[t] = n;
for(int i = 1; i <= t; ++i) {
mul[i] = 1;
for(int j = L[i]; j <= R[i]; ++j)
pos[j] = i;
}
for(int i = 1; i <= n; ++i) {
opt = read(), l = read(), r = read(), d = read();
if(!opt) change_add(l, r, d);
if(opt == 1) change_mul(l, r, d);
if(opt == 2) writeln((ll)(a[r] * mul[pos[r]] + add[pos[r]]) % mod);
}
return 0;
}

数列分块入门 8

给出一个长为 $n$ 的数列,以及 $n$ 个操作,操作涉及区间询问等于一个数 $c$ 的元素,并将这个区间的所有元素改为 $c$。

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
#include<bits/stdc++.h>
#define gc getchar
#define ll long long
inline ll read(){ll x = 0; char ch = gc(); bool positive = 1;for (; !isdigit(ch);
ch = gc()) if (ch == '-') positive = 0;for (; isdigit(ch); ch = gc()) x = x * 10
+ ch - '0';return positive ? x : -x;}inline void write(ll a){if(a>=10)write(a/10);
putchar('0'+a%10);}inline void writeln(ll a){if(a<0){a=-a; putchar('-');}write(a);
puts("");}
using namespace std;
const int N = 100010;
int a[N], n, t, L[N], R[N], pos[N], v[N];
bool flag[N];
int ask(int l, int r, int c) {
int p = pos[l], q = pos[r], res = 0;
if(p == q) {
if(flag[p]) {
for(int i = L[p]; i <= R[p]; ++i)
a[i] = v[p];
flag[p] = false;
}
for(int i = l; i <= r; ++i) {
res += a[i] == c;
a[i] = c;
}
} else {
for(int i = p + 1; i <= q - 1; ++i)
if(flag[i]) {
res += (v[i] == c) * (R[i] - L[i] + 1);
v[i] = c;
}
else {
for(int j = L[i]; j <= R[i]; ++j) {
res += a[j] == c;
a[j] = c;
}
v[i] = c;
flag[i] = true;
}
if(flag[p]) {
for(int i = L[p]; i <= R[p]; ++i) a[i] = v[p];
flag[p] = false;
}
for(int i = l; i <= R[p]; ++i) {
res += a[i] == c;
a[i] = c;
}
if(flag[q]) {
for(int i = L[q]; i <= R[q]; ++i) a[i] = v[q];
flag[q] = false;
}
for(int i = L[q]; i <= r; ++i) {
res += a[i] == c;
a[i] = c;
}
}
return res;
}
int main() {
int l, r, c;
n = read();
for(int i = 1; i <= n; ++i) a[i] = read();
t = sqrt(n);
for(int i = 1; i <= t; ++i) {
L[i] = (i - 1) * t + 1;
R[i] = i * t;
}
if(R[t] < n) L[++t] = R[t - 1] + 1, R[t] = n;
for(int i = 1; i <= t; ++i) {
flag[i] = true;
for(int j = L[i]; j <= R[i]; ++j) {
pos[j] = i;
if(j > L[i] && a[j] != a[j - 1]) flag[i] = false;
}
if(flag[i]) v[i] = a[L[i]];
}
for(int i = 1; i <= n; ++i) {
l = read(), r = read(), c = read();
writeln(ask(l, r, c));
}
return 0;
}