Submission #63711

ソースコード

?
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
125
126
127
128
#include <bits/stdc++.h>
using namespace std;
typedef long long SEGNODE_TYPE; // セグ木のノードの型の定義
class Segtree
{
public:
SEGNODE_TYPE monoid;
int segsize; // セグ木の大きさ
vector<SEGNODE_TYPE> value;
// [引数]
// int n : 大きさ
// SEGNODE_TYPE start : 初期値
// SEGNODE_TYPE mnd : 単位元（モノイド）
// [動作]
// セグ木を作る
// ※SEGNODE_TYPE の定義を忘れずに
Segtree() {}
Segtree(int n, SEGNODE_TYPE start, SEGNODE_TYPE mnd) {
segsize = 1;
while(segsize < n){
segsize = segsize * 2;
}
value = vector<SEGNODE_TYPE>(2 * segsize - 1, start);
monoid = mnd;
}
// [引数]
// int i : 変更箇所
// SEGNODE_TYPE x : 変更値
// [動作]
// 場所iをxに変更
void UpDate(int i, SEGNODE_TYPE 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 : 区間の右端
// int n : 全区間の幅
// [動作]
// 区間[a, b)のクエリを処理する（SegQueryへ橋渡し）
// ※呼び出す際にはSEGNODE_TYPE Requirement(SEGNODE_TYPE x, SEGNODE_TYPE y)の中身を確認
SEGNODE_TYPE Query(int a, int b, int n) {
return ( SegQuery(a, b+1, 0, 0, segsize) );
}
// [引数]
// int a : クエリの範囲の左端
// int b : クエリの範囲の右端
// int k : 今いるノードの場所
// int l : 今いるノードの参照範囲の左端
// int r : 今いるノードの参照範囲の右端
// [動作]
// 区間[a, b)のクエリを求める
SEGNODE_TYPE 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 {
// 左右の子に尋ねる
SEGNODE_TYPE c1 = SegQuery(a, b, 2*k+1, l, (l+r)/2); // 左の子（状況に合わせて型を変える）
SEGNODE_TYPE c2 = SegQuery(a, b, 2*k+2, (l+r)/2, r); // 右の子（状況に合わせて型を変える）
return ( Requirement(c1, c2) ); // 左右の子から求めたいものを返す
}
}
// 求めたいもの（最小値ならmin(x, y)、最大値ならmax(x, y)、合計値なら(x + y)など）
// ※ここのreturn文は用途に合わせて書き換える必要がある
SEGNODE_TYPE Requirement(SEGNODE_TYPE x, SEGNODE_TYPE y) {
return ( x + y );
}
// [引数]
// int i : 場所
// [動作]
// 左からi番目の値を変えす
SEGNODE_TYPE GetReaf(int i) {
return( value[i + segsize - 1] );
}
};
int main() {
int n, q, s;
cin >> n >> q;
Segtree tree = Segtree(n, 0, 0);
for ( int i = 0; i < q; i++ ) {
cin >> s;
if ( s == 0 ) {
int a;
long long b;
cin >> a >> b;
a--;
b += tree.GetReaf(a);
tree.UpDate(a, b);
} else {
int a, b;
cin >> a >> b;
a--, b--;
cout << tree.Query(a, b, n) << endl;
}
}
return (0);
}

ステータス

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

セット

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

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
input100-1 AC 110 ms 1496 KB
1
input100-2 AC 211 ms 4156 KB
1
input100-3 AC 423 ms 10008 KB
1
input100-4 AC 889 ms 22004 KB
1
input100-5 AC 1228 ms 33492 KB
1
input1000-1 AC 382 ms 35636 KB
1
input1000-2 AC 892 ms 40696 KB
1
input1000-3 AC 406 ms 42940 KB
1
input1000-4 AC 1095 ms 49408 KB
1
input1000-5 AC 343 ms 51140 KB
1
input10000-1 AC 1047 ms 57088 KB
1
input10000-2 AC 1132 ms 63452 KB
1
input10000-3 AC 890 ms 68284 KB
1
input10000-4 AC 1028 ms 73876 KB
1
input10000-5 AC 536 ms 76784 KB
1
input100000-1 AC 1243 ms 84940 KB
1
input100000-2 AC 206 ms 87080 KB
1
input100000-3 AC 222 ms 87936 KB
1
input100000-4 AC 645 ms 90068 KB
1
input100000-5 AC 1121 ms 95924 KB
1
input1000000-1 AC 155 ms 126612 KB
1
input1000000-2 AC 502 ms 127212 KB
1
input1000000-3 AC 570 ms 129356 KB
1
input1000000-4 AC 1082 ms 131748 KB
1
input1000000-5 AC 489 ms 136576 KB
1
input1001000-1 AC 19 ms 105952 KB
1
input1001000-2 AC 22 ms 105920 KB
1
input1001000-3 AC 23 ms 106012 KB
1
input1001000-4 AC 21 ms 105984 KB
1
input1001000-5 AC 23 ms 106208 KB
1