Submission #62114

ソースコード

?
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
#include<bits/stdc++.h>
using namespace std;
/*SegTree<x>(n,fx,ex): モノイド(集合X,二項演算fx,単位元ex)についてサイズnで構築
set(int i,X x),build(): i番目の要素をxにセット。まとめてセグ木を構築する0(n)
update(i,x): i番目の要素をxに更新。O(log(n))
query(a,b): [a,b) 全てにfxを作用させた値を取得。O(log(n))
operator[k] := k番目の要素を返す。
find_rightest : [a,b) で x以下の要素を持つ最右位置はどこか
find_leftest : [a,b) で x以下の要素を持つ最左位置はどこか
*/
template <typename X>
struct SegTree{
using FX=function<X(X,X)>; //X●X -> X となる関数の型
int n;
FX fx;
const X ex;
vector<X> dat;
SegTree(int size,FX fx_,X ex_) : n(),fx(fx_),ex(ex_),dat(size*4,ex_){
int x=1;
while(size>x){
x*=2;
}
n=x;
return;
}
void set(int i,X x){ dat[i+n-1]=x;}
void build(){
for(int k=n-2;k>=0;k--) dat[k]=fx(dat[2*k+1],dat[2*k+2]);
return;
}
void update(int i,X x){
i+=n-1;
dat[i]=x;
while(i>0){
i=(i-1)/2;
dat[i]=fx(dat[i*2+1],dat[i*2+2]);
}
return;
}
X query(int a,int b){ return (query_sub(a,b,0,0,n));}
X query_sub(int a,int b,int k,int l,int r){
if(r<=a || b<=l){
return ex;
}
else if(a<=l && r<=b){
return dat[k];
}
else{
X vl=query_sub(a,b,k*2+1,l,(l+r)/2);
X vr=query_sub(a,b,k*2+2,(l+r)/2,r);
return fx(vl,vr);
}
}
X operator[](const int &k) const{
return dat[k+n-1];
}
X find_rightest(int a, int b, X x) { return find_rightest_sub(a, b, x, 0, 0, n); }
X find_leftest(int a, int b, X x) { return find_leftest_sub(a, b, x, 0, 0, n); }
X find_rightest_sub(int a, int b, X x, int k, int l, int r) {
if (dat[k] > x || r <= a || b <= l) { // 自分の値がxより大きい or [a,b)が[l,r)の範囲外
return a - 1;
} else if (k >= n - 1) { // 自分が葉ならその位置をreturn
return (k - (n - 1));
} else {
int vr = find_rightest_sub(a, b, x, 2 * k + 2, (l + r) / 2, r);
if (vr != a - 1) { // 右の部分木を見て a-1 以外ならreturn
return vr;
} else { // 左の部分木を見て値をreturn
return find_rightest_sub(a, b, x, 2 * k + 1, l, (l + r) / 2);
}
}
}
X find_leftest_sub(int a, int b, X x, int k, int l, int r) {
if (dat[k] > x || r <= a || b <= l) { // 自分の値がxより大きい or [a,b)が[l,r)の範囲外
return b;
} else if (k >= n - 1) { // 自分が葉ならその位置をreturn
return (k - (n - 1));
} else {
int vl = find_leftest_sub(a, b, x, 2 * k + 1, l, (l + r) / 2);
if (vl != b) { // 左の部分木を見て b 以外ならreturn
return vl;
} else { // 右の部分木を見て値をreturn
return find_leftest_sub(a, b, x, 2 * k + 2, (l + r) / 2, r);
}
}
}
};
int main(){
int n,m;
cin>>n>>m;
auto fx=[](int x1,int x2) -> int {return min(x1,x2);};
int ex=numeric_limits<int>::max();
SegTree<int> minseg(n,fx,ex);
auto fx2=[](int x1,int x2) -> int {return max(x1,x2);};
int ex2=-ex;
SegTree<int> maxseg(n,fx2,ex2);
auto fx3=[](int x1,int x2) -> int {return (x1+x2);};
int ex3=0;
SegTree<int> sumseg(n,fx3,ex3);
string s;
int a,b;
for(int i=0;i<n;i++){
minseg.update(i,0);
maxseg.update(i,0);
sumseg.update(i,0);
}
for(int i=0;i<m;i++){
cin>>s>>a>>b;
if(s=="update"){
minseg.update(a,b);
maxseg.update(a,b);
sumseg.update(a,b);
}
else if(s=="add"){
minseg.update(a,minseg[a]+b);
maxseg.update(a,maxseg[a]+b);
sumseg.update(a,sumseg[a]+b);
}
else if(s=="getMin"){
cout<<minseg.query(a,b)<<'\n';
}
else if(s=="getMax"){
cout<<maxseg.query(a,b)<<'\n';
}
else{
cout<<sumseg.query(a,b)<<'\n';
}
}
return(0);
}

ステータス

項目 データ
問題 1072 - セグメントツリー技術基礎
ユーザー名 ei1918
投稿日時 2020-08-13 15:41:26
言語 C++14
状態 Accepted
得点 1
ソースコード長 4238 Byte
最大実行時間 209 ms
最大メモリ使用量 10752 KB

セット

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

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
in01 AC 28 ms 604 KB
1
in02 AC 130 ms 960 KB
1
in03 AC 112 ms 5296 KB
1
in04 AC 156 ms 5228 KB
1
in05 AC 63 ms 5644 KB
1
in06 AC 87 ms 3472 KB
1
in07 AC 114 ms 3196 KB
1
in08 AC 176 ms 2948 KB
1
in09 AC 167 ms 5452 KB
1
in10 AC 182 ms 3840 KB
1
in11 AC 43 ms 3360 KB
1
in12 AC 72 ms 2564 KB
1
in13 AC 160 ms 7248 KB
1
in14 AC 209 ms 4040 KB
1
in15 AC 121 ms 6872 KB
1
in16 AC 157 ms 3888 KB
1
in17 AC 148 ms 6764 KB
1
in18 AC 78 ms 8012 KB
1
in19 AC 140 ms 7452 KB
1
in20 AC 87 ms 7396 KB
1
in21 AC 106 ms 6548 KB
1
in22 AC 190 ms 6932 KB
1
in23 AC 138 ms 8792 KB
1
in24 AC 142 ms 7612 KB
1
in25 AC 164 ms 6032 KB
1
in26 AC 191 ms 9936 KB
1
in27 AC 162 ms 9952 KB
1
in28 AC 194 ms 7580 KB
1
in29 AC 71 ms 9520 KB
1
in30 AC 170 ms 10752 KB
1
in31 AC 104 ms 8420 KB
1
in32 AC 172 ms 8436 KB
1