Submission #71730

ソースコード

?
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
141
142
143
144
145
146
147
148
149
/**********************
* *
* セグ木テンプレ *
* *
**********************/
//1072 - セグメントツリー技術基礎
//参考 - ei2009
#include<bits/stdc++.h>
#define dou double
#define ll long long
#define int2 int,int
#define all(x) x.begin(),x.end()
#define gi greater<int>()
#define pb push_back
#define mp make_pair
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define fir first
#define sec second
#define uns unsigned
using namespace std;
struct seg{
int n,inf=30000,m_inf=-30000;
vector<ll> v_sum; //区間和
vector<ll> v_min; //最小値
vector<ll> v_max; //最大値
//配列初期化
seg(int size){
n=1;
while(n<size){
n*=2;
}
v_sum.resize(n*2);
v_min.resize(n*2);
v_max.resize(n*2);
for(int i=0;i<n*2;i++){
v_sum[i]=0;
v_min[i]=0;
v_max[i]=0;
}
}
//値の更新
void update(int i,int x){
i+=n-1;
v_sum[i]=x;
v_min[i]=x;
v_max[i]=x;
while(i>0){
i=(i-1)/2;
v_sum[i]=v_sum[i*2+1]+v_sum[i*2+2];
v_min[i]=min(v_min[i*2+1],v_min[i*2+2]);
v_max[i]=max(v_max[i*2+1],v_max[i*2+2]);
}
}
//値の加算
void add(int i,int x){
i+=n-1;
v_sum[i]+=x;
v_min[i]+=x;
v_max[i]+=x;
while(i>0){
i=(i-1)/2;
v_sum[i]=v_sum[i*2+1]+v_sum[i*2+2];
v_min[i]=min(v_min[i*2+1],v_min[i*2+2]);
v_max[i]=max(v_max[i*2+1],v_max[i*2+2]);
}
}
//最小値の取得
int getMin(int a,int b){
return getlit(a,b,0,0,n);
}
int getlit(int a,int b,int i,int l,int r){
if(r<=a||b<=l){ //完全に範囲外
return inf;
}else if(a<=l&&r<=b){ //完全に範囲内
return v_min[i];
}else{ //一部区間が被る
int min_l=getlit(a,b,i*2+1,l,(l+r)/2);
int min_r=getlit(a,b,i*2+2,(l+r)/2,r);
return min(min_l,min_r);
}
}
//最大値の取得
int getMax(int a,int b){
return getbig(a,b,0,0,n);
}
int getbig(int a,int b,int i,int l,int r){
if(r<=a||b<=l){
return m_inf;
}else if(a<=l&&r<=b){
return v_max[i];
}else{
int max_l=getbig(a,b,i*2+1,l,(l+r)/2);
int max_r=getbig(a,b,i*2+2,(l+r)/2,r);
return max(max_l,max_r);
}
}
//合計値(区間和)の取得
int getSum(int a,int b){
return gettot(a,b,0,0,n);
}
int gettot(int a,int b,int i,int l,int r){
if(r<=a||b<=l){
return 0;
}else if(a<=l&&r<=b){
return v_sum[i];
}else{
int sum_l=gettot(a,b,i*2+1,l,(l+r)/2);
int sum_r=gettot(a,b,i*2+2,(l+r)/2,r);
return sum_l+sum_r;
}
}
//出力用コード(最大値ver.)
void out(int size){
for(int i=n-1;i<size+n;i++){
cout<<v_sum[i]<<" ";
}
cout<<"\n";
}
};
int main(){
int n,m,a,b;
cin>>n>>m;
seg st(n);
string query;
for(int i=0;i<m;i++){
cin>>query>>a>>b;
if(query=="update") st.update(a,b);
else if(query=="add") st.add(a,b);
else if(query=="getMin") cout<<st.getMin(a,b)<<"\n";
else if(query=="getMax") cout<<st.getMax(a,b)<<"\n";
else if(query=="getSum") cout<<st.getSum(a,b)<<"\n";
}
//st.out(n);
return 0;
}
/*使うメリット
値が更新される時の最小値や累積和の取得。
通常累積和を求める時はO(N)かかるが、
セグ木を使うと0(log N)で行うことができる。
*/

ステータス

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

セット

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

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
in01 AC 25 ms 604 KB
1
in02 AC 133 ms 960 KB
1
in03 AC 104 ms 7136 KB
1
in04 AC 145 ms 7348 KB
1
in05 AC 58 ms 7432 KB
1
in06 AC 76 ms 4444 KB
1
in07 AC 102 ms 4532 KB
1
in08 AC 177 ms 3212 KB
1
in09 AC 151 ms 7900 KB
1
in10 AC 184 ms 5304 KB
1
in11 AC 46 ms 3856 KB
1
in12 AC 74 ms 2536 KB
1
in13 AC 142 ms 8844 KB
1
in14 AC 196 ms 4448 KB
1
in15 AC 117 ms 9144 KB
1
in16 AC 162 ms 3984 KB
1
in17 AC 132 ms 9576 KB
1
in18 AC 71 ms 9660 KB
1
in19 AC 141 ms 10004 KB
1
in20 AC 87 ms 10096 KB
1
in21 AC 97 ms 7116 KB
1
in22 AC 190 ms 7460 KB
1
in23 AC 119 ms 10620 KB
1
in24 AC 137 ms 7768 KB
1
in25 AC 149 ms 6580 KB
1
in26 AC 178 ms 11400 KB
1
in27 AC 151 ms 11484 KB
1
in28 AC 193 ms 8756 KB
1
in29 AC 67 ms 11920 KB
1
in30 AC 167 ms 12264 KB
1
in31 AC 101 ms 9280 KB
1
in32 AC 151 ms 9492 KB
1