Submission #74099

ソースコード

?
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
投稿日時 2023-01-17 17:00:49
言語 C++17
状態 Accepted
得点 1
ソースコード長 3938 Byte
最大実行時間 215 ms
最大メモリ使用量 38792 KB

セット

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

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
in01 AC 58 ms 604 KB
1
in02 AC 160 ms 1856 KB
1
in03 AC 139 ms 8676 KB
1
in04 AC 203 ms 10048 KB
1
in05 AC 49 ms 10260 KB
1
in06 AC 74 ms 7788 KB
1
in07 AC 100 ms 8520 KB
1
in08 AC 177 ms 8736 KB
1
in09 AC 188 ms 14584 KB
1
in10 AC 183 ms 13268 KB
1
in11 AC 46 ms 11952 KB
1
in12 AC 97 ms 11144 KB
1
in13 AC 178 ms 18344 KB
1
in14 AC 198 ms 15740 KB
1
in15 AC 132 ms 21068 KB
1
in16 AC 149 ms 17064 KB
1
in17 AC 173 ms 23808 KB
1
in18 AC 80 ms 24408 KB
1
in19 AC 141 ms 25524 KB
1
in20 AC 86 ms 26256 KB
1
in21 AC 119 ms 23908 KB
1
in22 AC 197 ms 25660 KB
1
in23 AC 139 ms 29716 KB
1
in24 AC 141 ms 27888 KB
1
in25 AC 155 ms 27596 KB
1
in26 AC 180 ms 33832 KB
1
in27 AC 164 ms 35332 KB
1
in28 AC 215 ms 34012 KB
1
in29 AC 67 ms 37552 KB
1
in30 AC 185 ms 38792 KB
1
in31 AC 106 ms 36704 KB
1
in32 AC 160 ms 38072 KB
1