3805. 环形数组
摘要
Title: 3805. 环形数组
Tag: 线段树、懒标记
Memory Limit: 64 MB
Time Limit: 1000 ms
Powered by:NEFU AB-IN
3805. 环形数组
-
题意
给定一个长度为 n的环形数组 a0,a1,…,an−1
现在要对该数组进行 m次操作。
操作分为以下两种：
增值操作 l r d，将区间 [l,r]上的每个元素都增加 d
求最小值操作 l r，输出区间 [l,r]内的所有元素的最小值。
注意，数组是环形的，所以当 n=5时，区间 [3,1]内的所有元素依次为 a3,a4,a0,a1 -
思路
线段树的讲解 link
显然这是一个区间修改，求区间最小值的线段树板子题
懒标记记录
设计到区间修改时，就需要懒标记dt！！因为如果不用懒标记的话，每次区间修改就要确定到叶节点，时间复杂度还是
其实按我的理解，懒标记其实就是将中间结点当成了叶节点，也就是当给的范围能包裹当前范围时，就停下，更新这个中间结点的属性（比如懒标记值，最小值），就像更新叶子结点一样
然后，每次更新和查询，也就是要涉及到打了懒标记下面的结点的值的时候，就要执行pushdown操作，也就是将父亲的账本清空，全部加在儿子的账本上，然后儿子也要因为更新了账本而更新自己的属性
下面我会放代码，还有线段树的带注释代码
-
代码
原代码
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/*
* @Author: NEFU AB-IN
* @Date: 2023-03-27 20:28:11
* @FilePath: \Acwing\3805\3805.cpp
* @LastEditTime: 2023-03-27 21:28:21
*/
using namespace std;
typedef pair<int, int> PII;
const int N = 2e5 + 10, INF = 0x3f3f3f3f;
struct sa
{
int l, r, dt, mn;
};
sa tr[N << 2];
int a[N];
void pushup(int p)
{
tr[p].mn = min(tr[ls].mn, tr[rs].mn);
}
void pushdown(int p)
{
tr[ls].dt += tr[p].dt;
tr[rs].dt += tr[p].dt;
tr[ls].mn += tr[p].dt;
tr[rs].mn += tr[p].dt;
tr[p].dt = 0;
}
void build(int p, int l, int r)
{
tr[p] = {l, r, 0, a[l]};
if (l == r)
return;
int mid = l + r >> 1;
build(ls, l, mid);
build(rs, mid + 1, r);
pushup(p);
}
void update(int p, int L, int R, int d)
{
if (tr[p].l >= L && tr[p].r <= R)
{
tr[p].dt += d;
tr[p].mn += d;
return;
}
int mid = tr[p].l + tr[p].r >> 1;
pushdown(p);
if (L <= mid)
update(ls, L, R, d);
if (R > mid)
update(rs, L, R, d);
pushup(p);
}
int query(int p, int L, int R)
{
if (tr[p].l >= L && tr[p].r <= R)
{
return tr[p].mn;
}
int mid = tr[p].l + tr[p].r >> 1;
pushdown(p);
int res = INF;
if (L <= mid)
res = min(res, query(ls, L, R));
if (R > mid)
res = min(res, query(rs, L, R));
return res;
}
int n, m;
signed main()
{
scanf("%lld", &n);
for (int i = 1; i <= n; i++)
scanf("%lld", &a[i]);
build(1, 1, n);
scanf("%lld", &m);
while (m--)
{
int l, r;
char c;
scanf("%lld %lld%c", &l, &r, &c);
l++, r++;
if (c == '\n')
{
if (l <= r)
printf("%lld\n", query(1, l, r));
else
printf("%lld\n", min(query(1, 1, r), query(1, l, n)));
}
else
{
int d;
scanf("%lld", &d);
if (l <= r)
update(1, l, r, d);
else
update(1, 1, r, d), update(1, l, n, d);
}
}
return 0;
}
带注释
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/*
* @Author: NEFU AB-IN
* @Date: 2023-03-27 20:28:11
* @FilePath: \Acwing\3805\3805.cpp
* @LastEditTime: 2023-03-27 21:28:21
*/
using namespace std;
typedef pair<int, int> PII;
const int N = 2e5 + 10, INF = 0x3f3f3f3f;
struct sa
{
int l, r, dt, mn;
};
sa tr[N << 2];
int a[N];
void pushup(int p)
{
tr[p].mn = min(tr[ls].mn, tr[rs].mn);
}
void pushdown(int p) // 父亲的帐加在儿子身上
{
tr[ls].dt += tr[p].dt;
tr[rs].dt += tr[p].dt;
// 儿子账本发生了变化，所以自身的属性也要变
tr[ls].mn += tr[p].dt;
tr[rs].mn += tr[p].dt;
// 父亲账本清0
tr[p].dt = 0;
}
void build(int p, int l, int r)
{
tr[p] = {l, r, 0, a[l]};
if (l == r) // 是叶子就返回
return;
int mid = l + r >> 1; // 不是叶子就裂开
build(ls, l, mid);
build(rs, mid + 1, r);
pushup(p);
}
void update(int p, int L, int R, int d) // 大写的L，R代表数组的区间LR
{
if (tr[p].l >= L && tr[p].r <= R) // 覆盖了区间就修改
{
tr[p].dt += d;
tr[p].mn += d;
return;
}
int mid = tr[p].l + tr[p].r >> 1; // 没覆盖就裂开
// 先pushdown，最后pushup
pushdown(p);
// 看mid在哪边子树里，就进哪边
if (L <= mid)
update(ls, L, R, d);
if (R > mid)
update(rs, L, R, d);
pushup(p);
}
int query(int p, int L, int R)
{
if (tr[p].l >= L && tr[p].r <= R)
{
return tr[p].mn;
}
int mid = tr[p].l + tr[p].r >> 1;
pushdown(p);
int res = INF;
if (L <= mid)
res = min(res, query(ls, L, R));
if (R > mid)
res = min(res, query(rs, L, R));
return res;
}
int n, m;
signed main()
{
scanf("%lld", &n);
for (int i = 1; i <= n; i++)
scanf("%lld", &a[i]);
build(1, 1, n);
scanf("%lld", &m);
while (m--)
{
int l, r;
char c;
scanf("%lld %lld%c", &l, &r, &c);
l++, r++;
if (c == '\n')
{
if (l <= r)
printf("%lld\n", query(1, l, r));
else
printf("%lld\n", min(query(1, 1, r), query(1, l, n)));
}
else
{
int d;
scanf("%lld", &d);
if (l <= r)
update(1, l, r, d);
else
update(1, 1, r, d), update(1, l, n, d);
}
}
return 0;
}