Submission #62178

ソースコード

?
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) << endl;
}
}
return (0);
}

ステータス

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

セット

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

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
input100-1 AC 83 ms 860 KB
1
input100-2 AC 186 ms 1836 KB
1
input100-3 AC 407 ms 4212 KB
1
input100-4 AC 760 ms 9020 KB
1
input100-5 AC 1201 ms 16140 KB
1
input1000-1 AC 359 ms 18136 KB
1
input1000-2 AC 856 ms 23192 KB
1
input1000-3 AC 381 ms 25432 KB
1
input1000-4 AC 1018 ms 31772 KB
1
input1000-5 AC 315 ms 33496 KB
1
input10000-1 AC 945 ms 39700 KB
1
input10000-2 AC 1039 ms 45920 KB
1
input10000-3 AC 809 ms 50732 KB
1
input10000-4 AC 936 ms 56436 KB
1
input10000-5 AC 486 ms 59332 KB
1
input100000-1 AC 1129 ms 67472 KB
1
input100000-2 AC 183 ms 68444 KB
1
input100000-3 AC 202 ms 69284 KB
1
input100000-4 AC 583 ms 72684 KB
1
input100000-5 AC 965 ms 78268 KB
1
input1000000-1 AC 141 ms 93196 KB
1
input1000000-2 AC 438 ms 95444 KB
1
input1000000-3 AC 506 ms 97824 KB
1
input1000000-4 AC 951 ms 102764 KB
1
input1000000-5 AC 419 ms 104892 KB
1
input1001000-1 AC 21 ms 88588 KB
1
input1001000-2 AC 21 ms 88668 KB
1
input1001000-3 AC 22 ms 88616 KB
1
input1001000-4 AC 18 ms 88696 KB
1
input1001000-5 AC 22 ms 88644 KB
1