Submission #62125

ソースコード

?
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
#include<bits/stdc++.h>
#define lol long long
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 Segment{
using FX=function<X(X,X)>; //X●X -> X となる関数の型
int n;
FX fx;
const X ex;
vector<X> dat;
Segment(int size,FX fx_,X ex_) : fx(fx_),ex(ex_){
n=1;
while(size>n){
n*=2;
}
dat.resize(n*2,ex_);
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 get(int a,int b){ return (get_sub(a,b+1,0,0,n));}
X get_sub(int a,int b,int k,int l,int r){
if(r<=a || b<=l) return ex;
if(a<=l && r<=b) return dat[k];
X vl=get_sub(a,b,k*2+1,l,(l+r)/2);
X vr=get_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);
}
}
}
};
signed main(){
cin.tie(0);
ios::sync_with_stdio(false);
auto fx1=[](int x1,int x2) -> int {return min(x1,x2);};
auto fx2=[](int x1,int x2) -> int {return max(x1,x2);};
auto fx3=[](int x1,int x2) -> int {return x1+x2;};
int n,m;
cin >>n>>m;
Segment<int> minst(n,fx1,(1LL<<31)-1);
Segment<int> maxst(n,fx2,-(1LL<<31)+1);
Segment<int> sumst(n,fx3,0);
for(int i=0;i<n;i++){
minst.set(i,0);
maxst.set(i,0);
sumst.set(i,0);
}
minst.build();
maxst.build();
sumst.build();
for(int i=0;i<m;i++){
string s;
int a,b;
cin >>s>>a>>b;
if(s=="update"){
minst.update(a,b);
maxst.update(a,b);
sumst.update(a,b);
}else if(s=="add"){
minst.update(a,minst[a]+b);
maxst.update(a,maxst[a]+b);
sumst.update(a,sumst[a]+b);
}else if(s=="getMin") cout <<minst.get(a,b-1)<<'\n';
else if(s=="getMax") cout <<maxst.get(a,b-1)<<'\n';
else if(s=="getSum") cout <<sumst.get(a,b-1)<<'\n';
}
return (0);
}

ステータス

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

セット

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

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
in01 AC 27 ms 600 KB
1
in02 AC 53 ms 676 KB
1
in03 AC 44 ms 3860 KB
1
in04 AC 56 ms 4052 KB
1
in05 AC 28 ms 4244 KB
1
in06 AC 36 ms 2776 KB
1
in07 AC 41 ms 2968 KB
1
in08 AC 57 ms 2524 KB
1
in09 AC 53 ms 5016 KB
1
in10 AC 56 ms 3800 KB
1
in11 AC 30 ms 2964 KB
1
in12 AC 32 ms 2384 KB
1
in13 AC 59 ms 5692 KB
1
in14 AC 57 ms 3840 KB
1
in15 AC 51 ms 6200 KB
1
in16 AC 48 ms 3836 KB
1
in17 AC 50 ms 6712 KB
1
in18 AC 43 ms 6780 KB
1
in19 AC 48 ms 6972 KB
1
in20 AC 38 ms 6904 KB
1
in21 AC 38 ms 5560 KB
1
in22 AC 57 ms 6004 KB
1
in23 AC 44 ms 7472 KB
1
in24 AC 47 ms 6256 KB
1
in25 AC 51 ms 5688 KB
1
in26 AC 73 ms 8312 KB
1
in27 AC 56 ms 8504 KB
1
in28 AC 68 ms 7288 KB
1
in29 AC 30 ms 9008 KB
1
in30 AC 54 ms 9072 KB
1
in31 AC 45 ms 7732 KB
1
in32 AC 52 ms 7928 KB
1