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
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
|
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
#define inf 0x3f3f3f3f
class tree
{
public:
struct node
{
node* father;//父节点
node* left;//左子树
node* right;//右子树
double max;//区间最大值
double min;//区间最小值
double sum;//区间和
int l, r;//区间端点
double lazy_add;//加法标记
double lazy_multiply;//乘法标记
node()//初始化
{
father = NULL;
left = NULL;
right = NULL;
l = -1;
r = -1;
max = -inf;
min = inf;
sum = inf;
lazy_add = 0;//即什么都没加
lazy_multiply = 1;//即什么都没乘
}
};
~tree()//删除整棵树
{
d_t(root);
}
//---------------------------------------------构造线段树--------------------------------------------------
void build(vector<double> num)
{
d_t(root);//删除旧树
nums = num;//赋新值
int size = nums.size() - 1;
int mid = size / 2;
root = new node;
root->l = 0;//根节点区间左端为0
root->r = size;//根节点区间右端为size
_build(root, 0, mid);//构建左子树
_build(root, mid + 1, size);//构建右子树
updata(root);//更新根节点的值
}
//-----------------------------------------------查询-----------------------------------------------------
double find(int l, int r, string mode)
{
if (mode == "max")//返回区间最大值
return finda(root, l, r);
if (mode == "min")//返回区间最小值
return findi(root, l, r);
if (mode == "sum")//返回区间和
return findu(root, l, r);
}
//----------------------------------------------区间加法--------------------------------------------------
void add(int l, int r, double k)//区间l~r内每个数加k
{
_add(root, l, r, k);
}
//----------------------------------------------区间减法--------------------------------------------------
void multiply(int l, int r, double k)//区间l~r内.每个数乘k
{
_multiply(root, l, r, k);
}
//--------------------------------------------输出整个区间-------------------------------------------------
void out()//输出线段树包含的数
{
_out(root);
cout << "\n";
}
private:
node* root;//根节点
vector<double>nums;//数据
//----------------------------------------------删除------------------------------------------------------
void d_t(node* p)
{
if (p == NULL) return;//啥毛没有,咋删?
if (p->left != NULL) d_t(p->left);//删除左子树
if (p->right != NULL) d_t(p->right);//删除右子树
delete p;//删除自己
}
//----------------------------------------------更新--------------------------------------------------------
void updata(node *p)
{
p->max = max(p->left->max, p->right->max);//更新最大值
p->min = min(p->left->min, p->right->min);//更新最小值
p->sum = p->left->sum + p->right->sum;//更新区间和
}
//----------------------------------------------构造---------------------------------------------------------
node* _build(node *t, int l, int r)
{
node* p = new node;//建立新节点
p->l = l;//区间左端点
p->r = r;//区右端点
p->father = t;//建立父子关系
if (t->left == NULL) t->left = p;//若t没有左子树,说明要构建的树为其左子树
else t->right = p;//反之,则为右子树
if (l == r)//若为叶子节点
{
p->max = nums[l];//三个一样
p->min = nums[l];
p->sum = nums[l];
return p;//返回节点地址
}
int mid = (r - l) / 2;
p->left=_build(p, l, l + mid);//构造左子树
p->right=_build(p, l + mid + 1, r);//构造右子树
updata(p);//更新
return p;
}
//---------------------------------------------传递标记---------------------------------------------------
void down(node* p)
{
if (p->lazy_add == 0 && p->lazy_multiply == 1) return;//若没有标记,传递啥?
if (p->left->l == p->left->r)//若为叶子结点,无需修改其标记(根本就没标记...)
{
p->left->max *= p->lazy_multiply;//先乘后加
p->left->min *= p->lazy_multiply;
p->left->sum *= p->lazy_multiply;
p->left->max += p->lazy_add;
p->left->min += p->lazy_add;
p->left->sum += p->lazy_add;
}
else//否则,先修改标记,再修改值
{
p->left->lazy_multiply *= p->lazy_multiply;//先乘后加
p->left->lazy_add *= p->lazy_multiply;
p->left->lazy_add += p->lazy_add;
p->left->max *= p->lazy_multiply;
p->left->min *= p->lazy_multiply;
p->left->sum *= p->lazy_multiply;
p->left->max += p->lazy_add;
p->left->min += p->lazy_add;
p->left->sum += p->lazy_add * (p->left->r - p->left->l + 1);//区间和增加传递的标记乘以区间节点个数
}
if (p->right->l == p->right->r)//同上(本来就是复制下来的...)
{
p->right->max *= p->lazy_multiply;
p->right->min *= p->lazy_multiply;
p->right->sum *= p->lazy_multiply;
p->right->max += p->lazy_add;
p->right->min += p->lazy_add;
p->right->sum += p->lazy_add;
}
else
{
p->right->lazy_multiply *= p->lazy_multiply;
p->right->lazy_add *= p->lazy_multiply;
p->right->lazy_add += p->lazy_add;
p->right->max *=p->lazy_multiply;
p->right->min *=p->lazy_multiply;
p->right->sum *=p->lazy_multiply;
p->right->max +=p->lazy_add;
p->right->min +=p->lazy_add;
p->right->sum +=p->lazy_add * (p->right->r - p->right->l + 1);
}
p->lazy_add = 0;//删除加法标记
p->lazy_multiply = 1;//删除乘法标记
}
//------------------------------------------------输出----------------------------------------------------
void _out(node* p)
{
if (p->l == p->r)//若为叶子节点,输出
{
cout << p->max << " ";
return;
}
down(p);//使用子树前先传递标记
_out(p->left);//输出左子树
_out(p->right);//输出右子树
}
//---------------------------------------------查询区间最大值----------------------------------------------
double finda(node *p, int l, int r)
{
if (p->l == l && p->r == r) return p->max;//若区间正正好完全重合,返回最大值
down(p);//使用子树前先传递标记
int mid = (p->r - p->l) / 2;
if (p->l <= l && p->r >= r)//若区间被完全包含
{
if (p->l + mid >= r) return finda(p->left, l, r);//待查询区间位于其左子树.查询左子树
if (p->l + mid < l) return finda(p->right, l, r);//待查询区间位于其右子树,查询右子树
return max(finda(p->left, l, p->l + mid), finda(p->right, p->l + mid + 1, r));//从中间切开,分别查询,返回最大值
}
return -inf;//防止破坏
}
//--------------------------------------------查询区间最小值-----------------------------------------------
double findi(node *p, int l, int r)
{
if (p->l == l && p->r == r) return p->min;//若区间正正好完全重合,返回最小值
down(p);//使用子树前先传递标记
int mid = (p->r - p->l) / 2;
if (p->l <= l && p->r >= r)//若区间被完全包含
{
if (p->l + mid >= r) return findi(p->left, l, r);//待查询区间位于其左子树,查询左子树
if (p->l + mid < l) return findi(p->right, l, r);//待查询区间位于其右子树,查询右子树
return min(findi(p->left, l, p->l + mid), findi(p->right, p->l + mid + 1, r));//从中间切开,分别查询,返回最小值
}
return inf;//防止破坏
}
//----------------------------------------------查询区间和------------------------------------------------
double findu(node *p, int l, int r)
{
if (p->l == l && p->r == r) return p->sum;//若区间正正好完全重合,返回区间和
down(p);//使用子树前先传递标记
int mid = (p->r - p->l) / 2;
if (p->l <= l && p->r >= r)//若区间被完全包含
{
if (p->l + mid >= r) return findu(p->left, l, r);//若待查询区间位于其左子树,查询左子树
if (p->l + mid < l) return findu(p->right, l, r);//若待查询区间位于其右子树,查询右子树
return findu(p->left, l, p->l + mid) + findu(p->right, p->l + mid + 1, r);//从中间切开,分别查询,返回和
}
return inf;//防止破坏
}
//---------------------------------------------区间加法---------------------------------------------------
void _add(node *p, int l, int r, double k)
{
if (p->l == l && p->r == r)//若区间完全重合
{
if (p->l != p->r) p->lazy_add += k;//若不是叶子结点,更新加法标记
p->min += k;//更新区间最小值
p->max += k;//更新区间最大值
p->sum += k * (p->r - p->l + 1);//更新区间和
return;
}
int mid = (p->r - p->l) / 2;
if (p->l <= l && p->r >= r)//若区间被包含
{
down(p);//使用子树前先传递标记
if (p->l + mid >= r) _add(p->left, l, r, k);//若区间完全位于其左子树,向左子树查找区间l~r并执行加法
else
if (p->l + mid < l) _add(p->right, l, r, k);//若区间完全位于其右子树,向右子树查找区间l~r并执行加法
else//从中间切开,分别执行加法
{
_add(p->left, l, p->l + mid, k);
_add(p->right, p->l + mid + 1, r, k);
}
}
updata(p);//更新
}
//----------------------------------------------区间乘法--------------------------------------------------
void _multiply(node *p, int l, int r, double k)
{
if (p->l == l && p->r == r)//若区间完全重合
{
if (p->l != p->r) p->lazy_multiply *= k;//若不是叶子结点,更新乘法标记
if (k >= 0)//若乘数为正
{
p->max *= k;//原来最大的还是最大的
p->min *= k;//原来最小的还是最小的
}
else
{
double max = p->max, min = p->min;//暂时储存
p->max = min * k;//原来最大的符号相反后变成最小的
p->min = max * k;//原来最小的符号相反后变为最大的
}
p->sum *= k;//更新区间和
p->lazy_add *= k;//更新加法标记(下面每个数要加的数也乘了k)
return;
}
int mid = (p->r - p->l) / 2;
if (p->l <= l && p->r >= r)//若区间被完全包含
{
down(p);//使用子节点前先更新标记
if (p->l + mid >= r) _multiply(p->left, l, r, k);//若待操作区间完全位于左子树,向左子树查询并进行区间乘法
else
if (p->l + mid < l) _multiply(p->right, l, r, k);//若待操作区间完全位于右子树,向右子树查询并进行区间乘法
else//从中间切开,分别进行操作
{
_multiply(p->left, l, p->l + mid, k);
_multiply(p->right, p->l + mid + 1, r, k);
}
}
updata(p);//更新
}
};
tree Te;
int main()
{
char D;
aaa:cin >> D;
switch (D)
{
case 'B'://构造
{
int n;
cin >> n;
vector<double> muns;
double num;
for (int i = 0; i < n; i++)
{
cin >> num;
muns.push_back(num);
}
Te.build(muns);
break;
}
case 'N'://查询区间最小值
{
int l, r;
cin >> l >> r;
cout << Te.find(l, r, "min") << endl;
break;
}
case 'M'://查询区间和
{
int l, r;
cin >> l >> r;
cout << Te.find(l, r, "sum") << endl;
break;
}
case 'X'://查询区间最大值
{
int l, r;
cin >> l >> r;
cout << Te.find(l, r, "max") << endl;
break;
}
case 'J'://区间加法
{
int l, r;
double k;
cin >> l >> r >> k;
Te.add(l, r, k);
break;
}
case 'C'://区间乘法
{
int l, r;
double k;
cin >> l >> r >> k;
Te.multiply(l, r, k);
break;
}
case 'O'://输出
{
Te.out();
break;
}
case 'E'://结束
{
return 0;
}
}
goto aaa;
return 0;
}
|
