今天我刷题了吗
搜索文档…
树状数组
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(5e5 + 10);
7
int c[maxn];
8
9
template<typename T = int>
10
inline const T read()
11
{
12
T x = 0, f = 1;
13
char ch = getchar();
14
while (ch < '0' || ch > '9') {
15
if (ch == '-') f = -1;
16
ch = getchar();
17
}
18
while (ch >= '0' && ch <= '9') {
19
x = (x << 3) + (x << 1) + ch - '0';
20
ch = getchar();
21
}
22
return x * f;
23
}
24
25
template<typename T>
26
inline void write(T x, bool ln)
27
{
28
if (x < 0) {
29
putchar('-');
30
x = -x;
31
}
32
if (x > 9) write(x / 10, false);
33
putchar(x % 10 + '0');
34
if (ln) putchar(10);
35
}
36
37
inline int lowbit(int x)
38
{
39
return x & -x;
40
}
41
42
void update(int p, int n, int v)
43
{
44
for (int i = p; i <= n; i += lowbit(i)) {
45
c[i] += v;
46
}
47
}
48
49
ll getSum(int p)
50
{
51
ll sum = 0;
52
while (p) {
53
sum += c[p];
54
p -= lowbit(p);
55
}
56
return sum;
57
}
58
59
ll query(int l, int r)
60
{
61
return getSum(r) - getSum(l - 1);
62
}
63
64
int main()
65
{
66
#ifdef ONLINE_JUDGE
67
#else
68
freopen("input.txt", "r", stdin);
69
#endif
70
ios::sync_with_stdio(false);
71
int n = read(), m = read();
72
for (int i = 1; i <= n; ++i) {
73
update(i, n, read());
74
}
75
while (m--) {
76
int op = read(), a = read(), b = read();
77
if (op == 1) {
78
update(a, n, b);
79
} else {
80
write(query(a, b), true);
81
}
82
}
83
return 0;
84
}
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(5e5 + 10);
7
int c[maxn];
8
9
template<typename T = int>
10
inline const T read()
11
{
12
T x = 0, f = 1;
13
char ch = getchar();
14
while (ch < '0' || ch > '9') {
15
if (ch == '-') f = -1;
16
ch = getchar();
17
}
18
while (ch >= '0' && ch <= '9') {
19
x = (x << 3) + (x << 1) + ch - '0';
20
ch = getchar();
21
}
22
return x * f;
23
}
24
25
template<typename T>
26
inline void write(T x, bool ln)
27
{
28
if (x < 0) {
29
putchar('-');
30
x = -x;
31
}
32
if (x > 9) write(x / 10, false);
33
putchar(x % 10 + '0');
34
if (ln) putchar(10);
35
}
36
37
inline int lowbit(int x)
38
{
39
return x & -x;
40
}
41
42
void update(int p, int n, int v)
43
{
44
for (int i = p; i <= n; i += lowbit(i)) {
45
c[i] += v;
46
}
47
}
48
49
ll getSum(int p)
50
{
51
ll sum = 0;
52
while (p) {
53
sum += c[p];
54
p -= lowbit(p);
55
}
56
return sum;
57
}
58
59
ll query(int l, int r)
60
{
61
return getSum(r) - getSum(l - 1);
62
}
63
64
int main()
65
{
66
#ifdef ONLINE_JUDGE
67
#else
68
freopen("input.txt", "r", stdin);
69
#endif
70
ios::sync_with_stdio(false);
71
int n = read(), m = read();
72
for (int i = 1; i <= n; ++i) {
73
update(i, n, read());
74
}
75
while (m--) {
76
int op = read(), a = read(), b = read();
77
if (op == 1) {
78
update(a, n, b);
79
} else {
80
write(query(a, b), true);
81
}
82
}
83
return 0;
84
}
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 a[maxn];
8
ll c[maxn][2];
9
10
template<typename T = int>
11
inline const T read()
12
{
13
T x = 0, f = 1;
14
char ch = getchar();
15
while (ch < '0' || ch > '9') {
16
if (ch == '-') f = -1;
17
ch = getchar();
18
}
19
while (ch >= '0' && ch <= '9') {
20
x = (x << 3) + (x << 1) + ch - '0';
21
ch = getchar();
22
}
23
return x * f;
24
}
25
26
template<typename T>
27
inline void write(T x, bool ln)
28
{
29
if (x < 0) {
30
putchar('-');
31
x = -x;
32
}
33
if (x > 9) write(x / 10, false);
34
putchar(x % 10 + '0');
35
if (ln) putchar(10);
36
}
37
38
inline int lowbit(int x)
39
{
40
return x & -x;
41
}
42
43
void add(int t, int p, int n, ll v)
44
{
45
for (int i = p; i <= n; i += lowbit(i)) {
46
c[i][t] += v;
47
}
48
}
49
50
ll getSum(int t, int p)
51
{
52
ll sum = 0;
53
for (int i = p; i; i -= lowbit(i)) {
54
sum += c[i][t];
55
}
56
return sum;
57
}
58
59
void update(int l, int r, int n, int v)
60
{
61
add(0, l, n, v);
62
add(0, r + 1, n, -v);
63
add(1, l, n, 1ll * v * (l - 1));
64
add(1, r + 1, n, -1ll * v * r);
65
}
66
67
ll query(int l, int r)
68
{
69
ll sum_r = 1ll * r * getSum(0, r) - getSum(1, r);
70
ll sum_l = 1ll * (l - 1) * getSum(0, l - 1) - getSum(1, l - 1);
71
return sum_r - sum_l;
72
}
73
74
int main()
75
{
76
#ifdef ONLINE_JUDGE
77
#else
78
freopen("input.txt", "r", stdin);
79
#endif
80
int n = read(), m = read();
81
for (int i = 1; i <= n; ++i) {
82
a[i] = read();
83
add(0, i, n, a[i] - a[i - 1]);
84
add(1, i, n, 1ll * (a[i] - a[i - 1]) * (i - 1));
85
}
86
while (m--) {
87
int op = read(), x = read(), y = read();
88
if (op == 1) {
89
int k = read();
90
update(x, y, n, k);
91
} else {
92
write(query(x, y), true);
93
}
94
}
95
return 0;
96
}
Copied!
最近更新 1yr ago
复制链接