Submission #62121

ソースコード

?
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 - セグメントツリー技術基礎
ユーザー名 immunity
投稿日時 2020-08-13 15:54:40
言語 C++17
状態 Accepted
得点 1
ソースコード長 4260 Byte
最大実行時間 210 ms
最大メモリ使用量 10756 KB

セット

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

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
in01 AC 26 ms 604 KB
1
in02 AC 133 ms 952 KB
1
in03 AC 120 ms 5416 KB
1
in04 AC 162 ms 5220 KB
1
in05 AC 62 ms 5764 KB
1
in06 AC 98 ms 3596 KB
1
in07 AC 104 ms 3320 KB
1
in08 AC 185 ms 3072 KB
1
in09 AC 164 ms 5320 KB
1
in10 AC 191 ms 3836 KB
1
in11 AC 50 ms 3364 KB
1
in12 AC 76 ms 2436 KB
1
in13 AC 157 ms 7120 KB
1
in14 AC 210 ms 4044 KB
1
in15 AC 132 ms 6880 KB
1
in16 AC 157 ms 3772 KB
1
in17 AC 153 ms 6776 KB
1
in18 AC 85 ms 8020 KB
1
in19 AC 154 ms 7336 KB
1
in20 AC 92 ms 7408 KB
1
in21 AC 108 ms 6560 KB
1
in22 AC 184 ms 6948 KB
1
in23 AC 145 ms 8556 KB
1
in24 AC 160 ms 7636 KB
1
in25 AC 156 ms 5928 KB
1
in26 AC 184 ms 9956 KB
1
in27 AC 172 ms 9968 KB
1
in28 AC 206 ms 7720 KB
1
in29 AC 73 ms 9656 KB
1
in30 AC 178 ms 10756 KB
1
in31 AC 99 ms 8420 KB
1
in32 AC 164 ms 8432 KB
1