Submission #77720

ソースコード

?
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
150
151
152
153
154
155
156
157
#include <bits/stdc++.h>
using namespace std;
class segtree{//基底クラス。セグ木の根幹
public: long long sz;
public: long long start = INT_MAX;
public: vector<long long>seg;
public: virtual void maketree(long long n,long long x,long long y){
start = x;
sz = 1;
while(sz < n){
sz <<= 1;
}
seg.assign((sz*2)-1,y);
}
public: virtual void lazy( long long x ){ return; }//遅延評価関数。遅延しない場合はreturn
public: virtual long long f( long long x , long long y ){ return min(x,y); }//更新関数。ここをoverrideで書き換えればOK
public: void update( long long a , long long b ){
a += sz-1;
lazy(a);
seg[a] = b;
while(a>0){
a = (a-1)>>1;
lazy((2*a)+1);
lazy ((2*a)+2);
seg[a] = f(seg[(2*a)+1],seg[(2*a)+2]);
}
}
public: void add(long long a,long long b){
a += sz-1;
lazy(a);
seg[a] += b;
while(a > 0){
a =(a-1)>>1;
lazy((2*a)+1);
lazy((2*a)+2);
seg[a] = f(seg[(2*a)+1],seg[(2*a)+2]);
}
}
public: long long rmq(long long a,long long b,long long k,long long l,long long r){
lazy(k);
if(a >= r||l >= b)return start;
if(a <= l&&b >= r)return seg[k];
return f(rmq(a,b,(k*2)+1,l,(l+r)>>1),rmq(a,b,(k*2)+2,(l+r)>>1,r));
}
public: long long rmq(long long a,long long b){return rmq(a,b,0,0,sz);}
};
class minseg : public segtree{//セグ木の派生クラス
public: minseg(long long n,long long y){maketree(n,INT_MAX,y);}
long long f(long long x,long long y) override { return min(x,y); };
};
class maxseg : public segtree{//セグ木の派生クラス
public: maxseg(long long n,long long y){maketree(n,-INT_MAX,y);}
long long f(long long x,long long y) override { return max(x,y); };
};
class sumseg : public segtree{//セグ木の派生クラス
public: sumseg(long long n,long long y){maketree(n,0,y);}
long long f(long long x,long long y) override { return x+y; };
};
class lazyseg : public segtree{//セグ木の派生クラス。遅セグ木の基底クラス
public: vector<long long>lazynum;
public: vector<bool>lazyflag;
public: void makelazytree(long long n,long long x,long long y){
maketree(n,x,y);
lazynum.assign((sz*2)-1,0);
lazyflag.assign((sz*2)-1,false);
lazynum[0] = 100;
lazyflag[0] = true;
}
public: virtual long long f2(long long x){return x;}//範囲加算用。伝播するときに渡す値。
public: virtual long long f4(long long x,long long y){return x;}//範囲加算用。計算時の計算
public: virtual void lazy(long long x) override {
if(lazyflag[x] == true){
lazyflag[x] = false;
seg[x] = f4(lazynum[x],seg[x]);
if(x < sz){
lazynum[(2*x)+1] = f2(lazynum[x]);
lazynum[(2*x)+2] = f2(lazynum[x]);
lazyflag[(2*x)+1] = true;
lazyflag[(2*x)+2] = true;
}
lazynum[x] = 0;
while(x > 0){
x = (x-1)>>1;
seg[x] = f(seg[(2*x)+1],seg[2*x+2]);
}
}
}
public: virtual long long f3(long long x,long long y){return x;}//範囲加算用。実際に入力する数。
public: virtual void areaupdate(long long a,long long b,long long k,long long l,long long r,long long x,long long y){
lazy(k);
if(a >= r||l >= b)return;
if(a <= l&&b >= r){
lazynum[k] = f3(x,y);
lazyflag[k] = true;
lazy(k);
return;
}
areaupdate(a,b,(k*2)+1,l,(l+r)>>1,x,y/2);
areaupdate(a,b,(k*2)+2,(l+r)>>1,r,x,y/2);
seg[k] = f(seg[(2*k)+1],seg[(2*k)+2]);
}
void areaupdate(long long a,long long b,long long x){return areaupdate(a,b,0,0,sz,x,sz);}
};
class minlazyseg : public lazyseg{//遅セグ木の派生クラス
public: minlazyseg(long long n,long long y){makelazytree(n,INT_MAX,y);}
long long f(long long x,long long y) override {return min(x,y);}
};
class sumlazyseg : public lazyseg{//遅セグの派生クラス。範囲加算
public: sumlazyseg(long long n,long long y){makelazytree(n,0,y);}
long long f(long long x,long long y) override {return x+y;}
long long f2(long long x) override {return x/2;}
long long f3(long long x,long long y) override {return x*y;}
long long f4(long long x,long long y) override {return x+y;}
};
int main(){
#define int long long
int n,m;
cin >>n>>m;
minseg T1(n,0);
maxseg T2(n,0);
sumseg T3(n,0);
for(int i = 0;i < m;i++){
string s;
cin >>s;
int x,y;
cin >>x>>y;
if(s == "getSum")cout <<T3.rmq(x,y)<<endl;
if(s == "getMax")cout <<T2.rmq(x,y)<<endl;
if(s == "getMin")cout <<T1.rmq(x,y)<<endl;
if(s == "add"){
T1.add(x,y);
T2.add(x,y);
T3.add(x,y);
}
if(s == "update"){
T1.update(x,y);
T2.update(x,y);
T3.update(x,y);
}
}
return 0;
}

ステータス

項目 データ
問題 1072 - セグメントツリー技術基礎
ユーザー名 ei2332
投稿日時 2024-04-12 19:32:55
言語 C++17
状態 Accepted
得点 1
ソースコード長 5414 Byte
最大実行時間 206 ms
最大メモリ使用量 12140 KB

セット

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

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
in01 AC 27 ms 600 KB
1
in02 AC 141 ms 824 KB
1
in03 AC 108 ms 6876 KB
1
in04 AC 164 ms 7092 KB
1
in05 AC 52 ms 7308 KB
1
in06 AC 74 ms 4324 KB
1
in07 AC 107 ms 4536 KB
1
in08 AC 176 ms 3084 KB
1
in09 AC 151 ms 8036 KB
1
in10 AC 182 ms 5304 KB
1
in11 AC 44 ms 3856 KB
1
in12 AC 82 ms 2664 KB
1
in13 AC 153 ms 8844 KB
1
in14 AC 206 ms 4584 KB
1
in15 AC 110 ms 9280 KB
1
in16 AC 148 ms 4244 KB
1
in17 AC 142 ms 9708 KB
1
in18 AC 70 ms 9792 KB
1
in19 AC 138 ms 10008 KB
1
in20 AC 90 ms 10100 KB
1
in21 AC 96 ms 7236 KB
1
in22 AC 180 ms 7456 KB
1
in23 AC 118 ms 10488 KB
1
in24 AC 137 ms 7764 KB
1
in25 AC 157 ms 6320 KB
1
in26 AC 186 ms 11268 KB
1
in27 AC 152 ms 11612 KB
1
in28 AC 189 ms 8888 KB
1
in29 AC 62 ms 12048 KB
1
in30 AC 157 ms 12140 KB
1
in31 AC 102 ms 9156 KB
1
in32 AC 151 ms 9752 KB
1