今天我刷题了吗
搜索文档…
线段树
1
#include <bits/stdc++.h>
2
3
using namespace std;
4
using ll = long long;
5
using p = pair<int, int>;
6
const int maxn(1e5 + 10);
7
8
struct node {
9
int l, r;
10
ll sum, lz;
11
} tree[maxn << 2];
12
13
template<typename T = int>
14
inline const T read()
15
{
16
T x = 0, f = 1;
17
char ch = getchar();
18
while (ch < '0' || ch > '9') {
19
if (ch == '-') f = -1;
20
ch = getchar();
21
}
22
while (ch >= '0' && ch <= '9') {
23
x = (x << 3) + (x << 1) + ch - '0';
24
ch = getchar();
25
}
26
return x * f;
27
}
28
29
template<typename T>
30
inline void write(T x, bool ln)
31
{
32
if (x < 0) {
33
putchar('-');
34
x = -x;
35
}
36
if (x > 9) write(x / 10, false);
37
putchar(x % 10 + '0');
38
if (ln) putchar(10);
39
}
40
41
inline int ls(int cur)
42
{
43
return cur << 1;
44
}
45
46
inline int rs(int cur)
47
{
48
return cur << 1 | 1;
49
}
50
51
void push_up(int cur)
52
{
53
tree[cur].sum = tree[ls(cur)].sum + tree[rs(cur)].sum;
54
}
55
56
void push_down(int cur)
57
{
58
if (tree[cur].lz) {
59
tree[ls(cur)].sum += (tree[ls(cur)].r - tree[ls(cur)].l + 1) * tree[cur].lz;
60
tree[rs(cur)].sum += (tree[rs(cur)].r - tree[rs(cur)].l + 1) * tree[cur].lz;
61
tree[ls(cur)].lz += tree[cur].lz;
62
tree[rs(cur)].lz += tree[cur].lz;
63
tree[cur].lz = 0;
64
}
65
}
66
67
void build(int cur, int l, int r)
68
{
69
tree[cur].l = l;
70
tree[cur].r = r;
71
tree[cur].lz = 0;
72
if (l == r) {
73
tree[cur].sum = read();
74
return;
75
}
76
int mid = (l + r) >> 1;
77
build(ls(cur), l, mid);
78
build(rs(cur), mid + 1, r);
79
push_up(cur);
80
}
81
82
void update(int cur, int l, int r, int v)
83
{
84
if (tree[cur].l == l and tree[cur].r == r) {
85
tree[cur].sum += (r - l + 1) * v;
86
tree[cur].lz += v;
87
return;
88
}
89
push_down(cur);
90
int mid = (tree[cur].l + tree[cur].r) >> 1;
91
if (r <= mid) {
92
update(ls(cur), l, r, v);
93
} else if (l > mid) {
94
update(rs(cur), l, r, v);
95
} else {
96
update(ls(cur), l, mid, v);
97
update(rs(cur), mid + 1, r, v);
98
}
99
push_up(cur);
100
}
101
102
ll query(int cur, int l, int r)
103
{
104
if (tree[cur].l == l and tree[cur].r == r) {
105
return tree[cur].sum;
106
}
107
push_down(cur);
108
int mid = (tree[cur].l + tree[cur].r) >> 1;
109
if (r <= mid) return query(ls(cur), l, r);
110
if (l > mid) return query(rs(cur), l, r);
111
return query(ls(cur), l, mid) + query(rs(cur), mid + 1, r);
112
}
113
114
int main()
115
{
116
#ifdef ONLINE_JUDGE
117
#else
118
freopen("input.txt", "r", stdin);
119
#endif
120
int n = read(), m = read();
121
build(1, 1, n);
122
while (m--) {
123
int t = read(), x = read(), y = read();
124
if (t == 1) {
125
int k = read();
126
update(1, x, y, k);
127
} else {
128
write(query(1, x, y), true);
129
}
130
}
131
return 0;
132
}
Copied!
1
#include <bits/stdc++.h>
2
3
using namespace std;
4
using ll = long long;
5
using p = pair<int, int>;
6
const int maxn(1e5 + 10);
7
int mod;
8
9
struct {
10
int l, r;
11
ll val, add, mult;
12
} tree[maxn << 2];
13
14
template<typename T = int>
15
inline const T read()
16
{
17
T x = 0, f = 1;
18
char ch = getchar();
19
while (ch < '0' || ch > '9') {
20
if (ch == '-') f = -1;
21
ch = getchar();
22
}
23
while (ch >= '0' && ch <= '9') {
24
x = (x << 3) + (x << 1) + ch - '0';
25
ch = getchar();
26
}
27
return x * f;
28
}
29
30
template<typename T>
31
inline void write(T x, bool ln)
32
{
33
if (x < 0) {
34
putchar('-');
35
x = -x;
36
}
37
if (x > 9) write(x / 10, false);
38
putchar(x % 10 + '0');
39
if (ln) putchar(10);
40
}
41
42
inline int ls(int cur)
43
{
44
return cur << 1;
45
}
46
47
inline int rs(int cur)
48
{
49
return cur << 1 | 1;
50
}
51
52
void push_up(int cur)
53
{
54
tree[cur].val = (tree[ls(cur)].val + tree[rs(cur)].val) % mod;
55
}
56
57
void push_down(int cur)
58
{
59
if (tree[cur].add or tree[cur].mult not_eq 1) {
60
tree[ls(cur)].val = ((tree[ls(cur)]).val * tree[cur].mult + (tree[ls(cur)].r - tree[ls(cur)].l + 1) * tree[cur].add) % mod;
61
tree[rs(cur)].val = ((tree[rs(cur)]).val * tree[cur].mult + (tree[rs(cur)].r - tree[rs(cur)].l + 1) * tree[cur].add) % mod;
62
tree[ls(cur)].mult = tree[ls(cur)].mult * tree[cur].mult % mod;
63
tree[rs(cur)].mult = tree[rs(cur)].mult * tree[cur].mult % mod;
64
tree[ls(cur)].add = (tree[ls(cur)].add * tree[cur].mult + tree[cur].add) % mod;
65
tree[rs(cur)].add = (tree[rs(cur)].add * tree[cur].mult + tree[cur].add) % mod;
66
tree[cur].add = 0;
67
tree[cur].mult = 1;
68
}
69
}
70
71
void build(int cur, int l, int r)
72
{
73
tree[cur].l = l;
74
tree[cur].r = r;
75
tree[cur].mult = 1;
76
if (l == r) {
77
tree[cur].val = read();
78
return;
79
}
80
int mid = (l + r) >> 1;
81
build(ls(cur), l, mid);
82
build(rs(cur), mid + 1, r);
83
push_up(cur);
84
}
85
86
void update(int cur, int l, int r, int op, int v)
87
{
88
if (tree[cur].l == l and tree[cur].r == r) {
89
if (op == 1) {
90
tree[cur].val = tree[cur].val * v % mod;
91
tree[cur].add = tree[cur].add * v % mod;
92
tree[cur].mult = tree[cur].mult * v % mod;
93
} else {
94
tree[cur].val = (tree[cur].val + (r - l + 1) * v) % mod;
95
tree[cur].add = (tree[cur].add + v) % mod;
96
}
97
return;
98
}
99
push_down(cur);
100
int mid = (tree[cur].l + tree[cur].r) >> 1;
101
if (r <= mid) {
102
update(ls(cur), l, r, op, v);
103
} else if (l > mid) {
104
update(rs(cur), l, r, op, v);
105
} else {
106
update(ls(cur), l, mid, op, v);
107
update(rs(cur), mid + 1, r, op, v);
108
}
109
push_up(cur);
110
}
111
112
ll query(int cur, int l, int r)
113
{
114
if (tree[cur].l == l and tree[cur].r == r) {
115
return tree[cur].val;
116
}
117
push_down(cur);
118
int mid = (tree[cur].l + tree[cur].r) >> 1;
119
if (r <= mid) {
120
return query(ls(cur), l, r);
121
}
122
if (l > mid) {
123
return query(rs(cur), l, r);
124
}
125
return (query(ls(cur), l, mid) + query(rs(cur), mid + 1, r)) % mod;
126
}
127
128
int main()
129
{
130
#ifdef ONLINE_JUDGE
131
#else
132
freopen("input.txt", "r", stdin);
133
#endif
134
int n = read(), m = read();
135
mod = read();
136
build(1, 1, n);
137
while (m--) {
138
int op = read(), x = read(), y = read();
139
if (op == 3) {
140
write(query(1, x, y), true);
141
} else {
142
update(1, x, y, op, read());
143
}
144
}
145
return 0;
146
}
Copied!
最近更新 1yr ago
复制链接