Submission #62227

ソースコード

?
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
#include <bits/stdc++.h>
using namespace std;
#define lol long long
class SegTreeSum
{
public:
lol monoid = 0; // モノイド ※型と値
lol start = 0; // 初期値 ※型と値
int segsize; // セグ木の大きさ
vector<lol> value;
SegTreeSum() {}
// [引数]
// int n : 大きさ
// [動作]
// セグ木を作る
SegTreeSum(int n) {
segsize = 1;
while(segsize < n){
segsize = segsize * 2;
}
value = vector<lol>(2 * segsize - 1, start);
}
// [引数]
// int i : 変更箇所
// int x : 変更値
// [動作]
// 場所iをxに変更
void UpDate(int i, lol x) {
i += segsize - 1;
value[i] = x;
while(i > 0){
i = (i-1) / 2;
value[i] = Requirement(value[i * 2 + 1], value[i * 2 + 2]);
}
return;
}
// [引数]
// int a : 区間の左端
// int b : 区間の右端
// [動作]
// 区間[a, b)の最小値を返す（SegQueryへ橋渡し）
lol Query(int a, int b) {
return ( SegQuery(a, b+1, 0, 0, segsize) );
}
// [引数]
// int a : クエリの範囲の左端
// int b : クエリの範囲の右端
// int k : 今いるノードの場所
// int l : 今いるノードの参照範囲の左端
// int r : 今いるノードの参照範囲の右端
// [動作]
// 区間[a, b)の最小値を返す
lol SegQuery(int a, int b, int k, int l, int r) {
// [a, b)の区間に対するクエリについて、ノードk(区間[l, r)担当)が答える
if(r <= a || b <= l) {
return (monoid);
}
if(a <= l && r <= b){
// ノードkの担当クエリ区間[a ,b)に完全に含まれる
return (value[k]);
}
else {
// 左右の子に尋ねる
lol c1 = SegQuery(a, b, 2*k+1, l, (l+r)/2); // 左の子（状況に合わせて型を変える）
lol c2 = SegQuery(a, b, 2*k+2, (l+r)/2, r); // 右の子（状況に合わせて型を変える）
return ( Requirement(c1, c2) ); // 左右の子から求めたいものを返す
}
}
// 求めたいもの（最小値ならmin(x, y)、最大値ならmax(x, y)、合計値なら(x + y)など）
lol Requirement(lol x, lol y) {
return ( x + y );
}
// [引数]
// int i : 場所
// [動作]
// 左からi番目の値を変えす
lol GetReaf(int i) {
return( value[i + segsize - 1] );
}
};
signed main()
{
cin.tie(nullptr);
ios_base::sync_with_stdio(false);
int n, q, s, a, b;
cin >> n >> q;
SegTreeSum tree = SegTreeSum(n);
for (int i=0 ;i<q ;i++ ) {
cin >> s >> a >> b;
if (s == 0) {
a--;
long long z = tree.GetReaf(a);
tree.UpDate(a, b+z);
}
else {
a --;
b --;
cout << tree.Query(a, b) << '\n';
}
}
return (0);
}

ステータス

項目 データ
問題 0649 - 区間和(セグ木、BIT練習)
ユーザー名 ei1929
投稿日時 2020-08-14 12:20:13
言語 C++17
状態 Accepted
得点 5
ソースコード長 3427 Byte
最大実行時間 332 ms
最大メモリ使用量 104896 KB

セット

セット 得点 Cases
1 ALL 5 / 5 *

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
input100-1 AC 35 ms 988 KB
1
input100-2 AC 51 ms 2080 KB
1
input100-3 AC 96 ms 4204 KB
1
input100-4 AC 158 ms 8888 KB
1
input100-5 AC 223 ms 16000 KB
1
input1000-1 AC 92 ms 18120 KB
1
input1000-2 AC 194 ms 23040 KB
1
input1000-3 AC 95 ms 25272 KB
1
input1000-4 AC 235 ms 31728 KB
1
input1000-5 AC 88 ms 33580 KB
1
input10000-1 AC 236 ms 39524 KB
1
input10000-2 AC 254 ms 45868 KB
1
input10000-3 AC 206 ms 50804 KB
1
input10000-4 AC 244 ms 56376 KB
1
input10000-5 AC 128 ms 59132 KB
1
input100000-1 AC 323 ms 67392 KB
1
input100000-2 AC 69 ms 68360 KB
1
input100000-3 AC 80 ms 69460 KB
1
input100000-4 AC 182 ms 72736 KB
1
input100000-5 AC 294 ms 78436 KB
1
input1000000-1 AC 62 ms 93352 KB
1
input1000000-2 AC 182 ms 95468 KB
1
input1000000-3 AC 184 ms 97840 KB
1
input1000000-4 AC 332 ms 102776 KB
1
input1000000-5 AC 150 ms 104896 KB
1
input1001000-1 AC 21 ms 88584 KB
1
input1001000-2 AC 19 ms 88660 KB
1
input1001000-3 AC 21 ms 88600 KB
1
input1001000-4 AC 28 ms 88548 KB
1
input1001000-5 AC 17 ms 88624 KB
1