Submission #71745

ソースコード

?
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
129
130
131
132
133
134
135
136
137
138
139
140
/*^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^\
< >
< >
< 解法の一例 >
< >
< >
\vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv*/
#include <bits/stdc++.h>
#define ll long long
using namespace std;
struct Segtree{
ll n;
vector<ll> vec_max; //最大値を求める用の配列
vector<ll> vec_min; //最小値
vector<ll> vec_sum; //総和
Segtree(ll size){
n=1;
while(n<size){
n*=2; //葉の数を決める
}
vec_max.resize(n*2); //resize要素数を変更
vec_min.resize(n*2);
vec_sum.resize(n*2);
for(ll i=0;i<n*2;i++){
vec_max[i]=0;
vec_min[i]=0;
vec_sum[i]=0;
}
}
// pos番目の値にvalueを足す
void update(ll pos,ll value){ //値の更新
pos+=n-1;
vec_max[pos]=value;
vec_min[pos]=value;
vec_sum[pos]=value;
while(pos>0){
pos=(pos-1)/2; //親を求める公式
vec_max[pos]=max(vec_max[pos*2+1],vec_max[pos*2+2]); //親を求める公式
vec_min[pos]=min(vec_min[pos*2+1],vec_min[pos*2+2]);
vec_sum[pos]=vec_sum[pos*2+1]+vec_sum[pos*2+2];
}
}
// pos番目の値にvalueを足す
void add(ll pos,ll value){ //値の更新
pos+=n-1;
vec_max[pos]+=value;
vec_min[pos]+=value;
vec_sum[pos]+=value;
while(pos>0){
pos=(pos-1)/2; //親を求める公式
vec_max[pos]=max(vec_max[pos*2+1],vec_max[pos*2+2]); //親を求める公式
vec_min[pos]=min(vec_min[pos*2+1],vec_min[pos*2+2]);
vec_sum[pos]=vec_sum[pos*2+1]+vec_sum[pos*2+2];
}
}
// a ~ b-1 までの区間の最小値を求める
ll getMin(ll a,ll b){
return getmin(a,b,0,0,n);
}
ll getmin(ll a,ll b,ll i,ll l,ll r){
if(b<=l||r<=a){ //見ている所が完全に範囲外
return LONG_LONG_MAX;
}
if(a<=l&&r<=b){ //..範囲内
return vec_min[i];
}else{
ll le=getmin(a,b,i*2+1,l,(l+r)/2); //左の子
ll ri=getmin(a,b,i*2+2,(l+r)/2,r); //右の子
return min(le,ri); //左と右の最小値
}
}
// a ~ b-1 までの区間の最大値を求める
ll getMax(ll a,ll b){
return getmax(a,b,0,0,n);
}
ll getmax(ll a,ll b,ll i,ll l,ll r){
if(b<=l||r<=a){ //見ている所が完全に範囲外
return LONG_LONG_MIN;
}
if(a<=l&&r<=b){ //..範囲内
return vec_max[i];
}else{
ll le=getmax(a,b,i*2+1,l,(l+r)/2); //左の子
ll ri=getmax(a,b,i*2+2,(l+r)/2,r); //右の子
return max(le,ri); //左と右の最大値
}
}
// a ~ b-1 までの区間の総和を求める
ll getSum(ll a,ll b){
return getsum(a,b,0,0,n);
}
ll getsum(ll a,ll b,ll i,ll l,ll r){
if(b<=l||r<=a){ //見ている所が完全に範囲外
return 0;
}
if(a<=l&&r<=b){ //..範囲内
return vec_sum[i];
}else{
ll le=getsum(a,b,i*2+1,l,(l+r)/2); //左の子
ll ri=getsum(a,b,i*2+2,(l+r)/2,r); //右の子
return le+ri; // 総和
}
}
};
signed main(){
cin.tie(nullptr);
ios_base::sync_with_stdio(false);
ll n, m;
cin>>n>>m;
Segtree seguki(n);
ll c[n],a,b;
for(ll i=0;i<m;i++){
string s;
cin>>s;
ll pos,value;
cin>>pos>>value;
if(s=="update"){
seguki.update(pos, value);
}else if(s=="add"){
seguki.add(pos, value);
}else if(s=="getMin"){
cout << seguki.getMin(pos, value) << '\n';
}else if(s=="getMax"){
cout << seguki.getMax(pos, value) << '\n';
}else{
cout << seguki.getSum(pos, value) << '\n';
}
}
return (0);
}

ステータス

項目 データ
問題 1072 - セグメントツリー技術基礎
ユーザー名 ei2134
投稿日時 2022-08-09 11:58:15
言語 C++17
状態 Accepted
得点 1
ソースコード長 4334 Byte
最大実行時間 68 ms
最大メモリ使用量 12232 KB

セット

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

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
in01 AC 24 ms 476 KB
1
in02 AC 43 ms 944 KB
1
in03 AC 48 ms 7100 KB
1
in04 AC 48 ms 7296 KB
1
in05 AC 34 ms 7360 KB
1
in06 AC 34 ms 4484 KB
1
in07 AC 41 ms 4548 KB
1
in08 AC 59 ms 3332 KB
1
in09 AC 51 ms 8264 KB
1
in10 AC 52 ms 5384 KB
1
in11 AC 24 ms 3912 KB
1
in12 AC 29 ms 2628 KB
1
in13 AC 65 ms 8852 KB
1
in14 AC 58 ms 4560 KB
1
in15 AC 46 ms 9236 KB
1
in16 AC 48 ms 4048 KB
1
in17 AC 45 ms 9612 KB
1
in18 AC 31 ms 9800 KB
1
in19 AC 49 ms 9988 KB
1
in20 AC 36 ms 10052 KB
1
in21 AC 42 ms 7172 KB
1
in22 AC 54 ms 7364 KB
1
in23 AC 50 ms 10628 KB
1
in24 AC 46 ms 7744 KB
1
in25 AC 56 ms 6528 KB
1
in26 AC 67 ms 11332 KB
1
in27 AC 53 ms 11528 KB
1
in28 AC 61 ms 8780 KB
1
in29 AC 35 ms 11916 KB
1
in30 AC 68 ms 12232 KB
1
in31 AC 50 ms 9352 KB
1
in32 AC 55 ms 9672 KB
1