线段树的使用场景#

线段树是一种常用来维护 区间信息 的数据结构

可以在极快的时间内实现单点修改、区间修改、单点查询、区间查询（区间求和，求区间的最大值，求区间的最小值）等操作

线段树的时间复杂度为 $O(nlogn)$ ，但具有很大的常数，一般能够适用于 $10^6$ 数据规模的题．

线段树的空间复杂度为 $O(n)$ ，但也具有很大的常数（一般大于 10）

基础线段树#

题目：P3372 线段树 1

如题，已知一个数列 $\{a_i\}$ 共 $n$ 项，你需要进行 $m$ 次下面两种操作：

将某区间每一个数加上 $k$ ．
求出某区间每一个数的和．

对于 $100\%$ 的数据： $1 \le n, m \le {10}^5$ ， $a_i,k$ 为正数，且任意时刻数列的和不超过 $2\times 10^{18}$ ．

思路#

如下图所示，线段树是建立在区间基础上的树，树的每个节点都代表着一段区间【L，R】，之后，在程序中维护每一个节点的信息．

将所有的节点从 $1$ 到 $2n-1$ 进行标号，则不难得出以下性质：

对于节点 $t$ ，设其区间为 $[l,r]$ ，定义 $mid = (l + r) \div 2$ ，则其子节点有两个，其一为节点 $2t$ ，其区间为 $[l, mid]$ ，其一为节点 $2t+1$ ，其区间为 $[mid+1, r]$ ，此外，当且仅当 $l = r$ 时，该节点为叶子节点，没有子节点．

代码实现#

建树#

首先，我们在建树的时候，可以考虑递归建树．

对于每一个节点，如果它是叶子节点，可以直接通过 a 数组设置基础信息，如果其下还有节点，则将该区间从中点处分割为两个子区间，并分别进入左右节点的递归建树，最后将两个子节点的信息 pushup 到父节点，即收集子节点的所有 sum 之和，来刷新父节点的元素和．

额外要注意的是，节点数组需要开至少 4 倍，这是由于线段树的二分特性，所以线段树的有效节点是 $2n-1$ ，但是，在下文的一些操作中，可能会访问到叶子节点的子节点，所以至少开 4 倍，这里建议开 8 倍，为了防止不必要的下标越界．

1
const int N = 1e5 + 100;
2
int a[N];
3
int sum[N * 8], add[N * 8];
4
// sum[i]表示第i个节点内，所有数之和
5
// add[i]（标记）表示在第i个节点内，需要对每一个数增加的数量，需要注意的是，在add数组更改时，sum数组也会同步更改，实际上，add数组储存的是该节点的所有子节点所需要增加的数量
6
void build(int t, int l, int r)
7
{
8
  // 需要：使用a数组来初始化sum数组
9
  // 如是最底层，单个的，则直接赋值
10
  if (l == r)
11
  {
12
    sum[t] = a[l];
13
    return;
14
  }
15
  // 否则，使用递归来为sum赋值
16
  int mid = (l + r) / 2;
17
  build(2 * t, l, mid);
18
  build(2 * t + 1, mid + 1, r);
19
  // 下层节点的贡献汇入本节点
20
  pushup(t);
21
}
22
// 下层节点的贡献汇入本节点
23
void pushup(int t)
24
{
25
  sum[t] = sum[2 * t] + sum[2 * t + 1];
26
}

区间修改#

对于一个节点 $t$ ，我们可以尝试实现一个函数，用于让该节点和目标区间重合的部分进行修改．在此题中，我们需要刷新第 $t$ 个节点，其起屹位置分别为 $l$ 和 $r$ ，使得区间 $[x,y] \cap [l,r]$ 中的每一个数增加 $k$ ．

首先的首先，我们需要让节点 $t$ 没有向下处理的所有标记（即记录在 add 数组中的）都推到节点 $t$ 的两个子节点上，并且要让子节点根据 add 来更新 sum，这个操作叫做 pushdown．更加普遍的，pushdown 就是让一个节点的所有的修改标记都释放给子节点，并且为子结点结算所有受到影响的查询标记．一个节点的修改标记会在施加后立即对查询标记生效，千万不要重复生效．

如果节点 $t$ 完全包含在了目标区间中（也就是说， $[l,r]\subseteq[x,y]$ ，即满足 $l \geq x \land r \leq y$ ），我们就要对该节点的 sum 值进行修正，此节点的每一个值都要增加 $k$ ，则这个节点的 sum 值就要有几个数就加几个 $k$ ，即需要增加的值 $\Delta = k(r-l+1)$ ，按道理来说，我需要将节点 $t$ 的所有子节点都进行更改，但是先放一放，暂且记在 add 中，作为标记．

如果节点 $t$ 与目标区间毫不相干（也就是说， $[x,y] \cap [l,r] = \varnothing$ ，即满足 $l > y \lor r < x$ ），则无需做任何处理，直接 return．

否则，表示节点 $t$ 与目标区间有重合部分，也间接表明了节点 $t$ 不是叶子节点，则可以递归处理，最后再将两个子节点的信息 pushup 到父节点．

1
void pushdown(int t, int l, int r)
2
{
3
  if (add[t])
4
  {
5
    // 处理add数组
6
    add[t * 2] += add[t];
7
    add[t * 2 + 1] += add[t];
8
    // 连带处理sum数组
9
    int mid = (l + r) / 2;
10
    sum[t * 2] += (mid - l + 1) * add[t];
11
    sum[t * 2 + 1] += (r - mid) * add[t];
12
    add[t] = 0;
13
  }
14
}
15
/// 尝试在t=>(l, r)这个范围内为[x,y]增加k
16
void Modify(int t, int l, int r, int x, int y, int k)
17
{
18
  // 先清理干净
19
  pushdown(t, l, r);
20
  // 检查能否完全包含
21
  if (l >= x && r <= y)
22
  {
23
    add[t] += k;
24
    sum[t] += k * (r - l + 1);
25
    return;
26
  }
27
  // 检查是否毫不相干
28
  if (l > y || r < x)
29
  {
30
    return;
31
  }
32
  // 否则，尝试委托给子节点
33
  int mid = (l + r) / 2;
34
  Modify(t * 2, l, mid, x, y, k);
35
  Modify(t * 2 + 1, mid + 1, r, x, y, k);
36
  // 收获成果
37
  pushup(t);
38
}

区间查询#

和修改很类似．

对于一个节点 $t$ ，我们可以尝试实现一个返回值为 int 的函数，用于让该节点和目标区间重合的部分进行修改．在此题中，我们需要查询第 $t$ 个节点，其起屹位置分别为 $l$ 和 $r$ ，获得区间 $[x,y] \cap [l,r]$ 中的每一个数增加 $k$ ．

首先的首先，我们需要先进行一次 pushdown，将自己身上撇干净．

如果节点 $t$ 完全包含在了目标区间中，我们就需要返回该节点中的元素的和，即 sum[t]．

如果节点 $t$ 与目标区间毫不相干，则直接 return 0．

否则，表示节点 $t$ 与目标区间有重合部分，也间接表明了节点 $t$ 不是叶子节点，则可以递归处理，最后再将两个子节点的信息相加返回．

1
/// @brief 尝试得到[l,r]和[x,y]之间的并集的元素之和
2
int Query(int t, int l, int r, int x, int y)
3
{
4
  // 先清理干净
5
  pushdown(t, l, r);
6
  // 检查能否完全包含
7
  if (l >= x && r <= y)
8
  {
9
    return sum[t];
10
  }
11
  // 检查是否毫不相干
12
  if (l > y || r < x)
13
  {
14
    return 0;
15
  }
16
  // 否则，尝试委托给子节点
17
  int mid = (l + r) / 2;
18
  return Query(t * 2, l, mid, x, y) + Query(t * 2 + 1, mid + 1, r, x, y);
19
}

标程#

1
#include <bits/stdc++.h>
2
using namespace std;
3

4
const int N = 1e5 + 100;
5

6
#define int long long
7

8
int n, m, a[N];
9
int sum[N * 8], add[N * 8];
10

11
class SegTree
12
{
13
private:
14
  // 初始化节点
15
  void build(int t, int l, int r)
16
  {
17
    // 需要：使用a数组来初始化sum数组
18
    // 如是最底层，单个的，则直接赋值
19
    if (l == r)
20
    {
21
      sum[t] = a[l];
22
      return;
23
    }
24
    // 否则，使用递归来为sum赋值
25
    int mid = (l + r) / 2;
26
    build(2 * t, l, mid);
27
    build(2 * t + 1, mid + 1, r);
28
    // 下层节点的贡献汇入本节点
29
    pushup(t);
30
  }
31
  // 下层节点的贡献汇入本节点
32
  void pushup(int t)
33
  {
34
    sum[t] = sum[2 * t] + sum[2 * t + 1];
35
  }
36
  // 将当前节点的add委派给子节点，调整子节点的add & sum
37
  void pushdown(int t, int l, int r)
38
  {
39
    if (add[t])
40
    {
41
      // 处理add数组
42
      add[t * 2] += add[t];
43
      add[t * 2 + 1] += add[t];
44
      // 连带处理sum数组
45
      int mid = (l + r) / 2;
46
      sum[t * 2] += (mid - l + 1) * add[t];
47
      sum[t * 2 + 1] += (r - mid) * add[t];
48
      add[t] = 0;
49
    }
50
  }
51

52
public:
53
  void Init()
54
  {
55
    build(1, 1, n);
56
  }
57
  /// @brief 尝试在t=>(l, r)这个范围内为[x,y]增加k
58
  void Modify(int t, int l, int r, int x, int y, int k)
59
  {
60
    // 先清理干净
61
    pushdown(t, l, r);
62
    // 检查能否完全包含
63
    if (l >= x && r <= y)
64
    {
65
      add[t] += k;
66
      sum[t] += k * (r - l + 1);
67
      return;
68
    }
69
    // 检查是否毫不相干
70
    if (l > y || r < x)
71
    {
72
      return;
73
    }
74
    // 否则，尝试委托给子节点
75
    int mid = (l + r) / 2;
76
    Modify(t * 2, l, mid, x, y, k);
77
    Modify(t * 2 + 1, mid + 1, r, x, y, k);
78
    // 收获成果
79
    pushup(t);
80
  }
81
  /// @brief 尝试得到[l,r]和[x,y]之间的并集的元素之和
82
  int Query(int t, int l, int r, int x, int y)
83
  {
84
    // 先清理干净
85
    pushdown(t, l, r);
86
    // 检查能否完全包含
87
    if (l >= x && r <= y)
88
    {
89
      return sum[t];
90
    }
91
    // 检查是否毫不相干
92
    if (l > y || r < x)
93
    {
94
      return 0;
95
    }
96
    // 否则，尝试委托给子节点
97
    int mid = (l + r) / 2;
98
    return Query(t * 2, l, mid, x, y) + Query(t * 2 + 1, mid + 1, r, x, y);
99
  }
100
};
101

102
signed main()
103
{
104
  cin >> n >> m;
105
  for (int i = 1; i <= n; i++)
106
    cin >> a[i];
107
  SegTree st;
108
  st.Init();
109
  for (int i = 1; i <= m; i++)
110
  {
111
    int op;
112
    cin >> op;
113
    if (op == 1)
114
    {
115
      int x, y, k;
116
      cin >> x >> y >> k;
117
      st.Modify(1, 1, n, x, y, k);
118
    }
119
    if (op == 2)
120
    {
121
      int x, y;
122
      cin >> x >> y;
123
      cout << st.Query(1, 1, n, x, y) << endl;
124
    }
125
  }
126
}

带有多种修改和查询操作的线段树#

题目：P3373 线段树 2

已知一个数列 $n$ 个数，你需要进行 $q$ 次下面三种操作：

将区间 $[x,y]$ 每一个数乘上 $k$ ；
将区间 $[x,y]$ 每一个数加上 $k$ ；
求出某区间每一个数的和对 $m$ 取模的结果．

对于 $100\%$ 的数据： $1 \le n \le 10^5$ ， $1 \le q \le 10^5,1\le k\le 10^4,m = 571373$ ．

思路#

对于多种查询的线段树，对每一种查询，给每一个节点设立一个对应的编辑，然后在 pushup 和 pushdown 中分别维护其添加、生效及移除即可．

对于多种改动的线段树，对每一种改动，先找出改动的优先级，然后再找到改动后对其余两种改动的影响．

就像此题，此题有两种改动，加法和乘法，如果对于某一个节点，其乘法标记增加了 $k$ ，那么其加法标记就会增加 $xk$ ，其中， $x$ 是原本就有的加法标记数量．

容易发现，乘法对加法的影响很容易确定，但是，如果对于某一个节点，其加法标记增加了 $k$ ，那么我们就很难确定其乘法标记增加多少．（也许是 $(x+k)\div k$ ，其中， $x$ 是原本就有的加法标记数量，但却大概率是个小数）

所以，我们在处理加法标记时，最好没有乘法标记（即乘法标记为 1），因此，乘法的优先级就大于加法．

与此同时，如果有一个操作“覆盖”，能进行区间的覆盖操作，那么很容易就可以知道，覆盖操作的优先级是大于乘法的．

因此，我们在 pushup 中只处理子节点提供给父节点的查询标记，而在 pushdown 中依照优先级处理父节点传递给子节点的所有标记及其影响，并清空父节点的标记．

对于此题，每一个节点都有 1 个查询标记 sum 和 2 个修改标记 add 与 mul．

标程#

1
#include <bits/stdc++.h>
2
using namespace std;
3
const int N = 1e5 + 10;
4
int n, q, m;
5
int a[N], sum[N * 8], add[N * 8], mul[N * 8];
6
// sum[i]表示第i个区间内，所有数之和
7
// add[i]（标记）表示在第i个区间内，需要对每一个数增加的数量，需要注意的是，在add数组更改时，sum数组也会同步更改，实际上，add数组储存的是该节点的所有子节点所需要增加的数量
8
// mul[i]（标记）与add类似，储存的是该节点的所有子节点所需要乘的倍数
9
// 此外，由于在访问左节点和右节点时，可能会访问到边界之外的值，所以，建议上述三个数组都要开8倍最大n的大小
10

11
// 定义一个类，用来表示线段树
12
class SegTree
13
{
14
private:
15
  /// @brief 通过t节点的所有子节点的sum值，将节点t的sum值进行刷新（收作业）
16
  /// @param t 目标节点
17
  /// @param l 节点t的左边界
18
  /// @param r 节点t的右边界
19
  void pushup(int t, int l, int r)
20
  {
21
    sum[t] = sum[t * 2] + sum[t * 2 + 1];
22
  }
23
  /// @brief 将t节点所有的标记都下放到其子节点，并在其子节点进行标记的结算
24
  /// @param t 目标节点
25
  /// @param l 节点t的左边界
26
  /// @param r 节点t的右边界
27
  void pushdown(int t, int l, int r)
28
  {
29
    // 由于mul[t]的默认值为1，所以不要写成以下代码
30
    // if (mul[t])
31
    if (mul[t] != 1) // 如果存在乘法标记
32
    {
33
      // 将乘法标记下放
34
      mul[t * 2] += mul[t];
35
      mul[t * 2 + 1] += mul[t];
36

37
      // 对应的，刷新add标记
38
      add[t * 2] *= mul[t];
39
      add[t * 2 + 1] *= mul[t];
40

41
      // 对应的，刷新sum标记
42
      sum[t * 2] *= mul[t];
43
      sum[t * 2 + 1] *= mul[t];
44

45
      // mul[t]恢复默认值
46
      mul[t] = 1;
47
    }
48

49
    if (add[t]) // 如果存在加法标记
50
    {
51
      // 将加法标记下放
52
      add[t * 2] += add[t];
53
      add[t * 2 + 1] += add[t];
54

55
      // 对应的，刷新sum标记
56
      int mid = (l + r) / 2;
57
      sum[t * 2] += add[t] * (mid - l + 1);
58
      sum[t * 2 + 1] += add[t] * (r - mid);
59

60
      // add标记恢复默认
61
      add[t] = 0;
62
    }
63
  }
64

65
public:
66
  /// @brief 构造一棵线段树的节点t
67
  /// @param t 目标节点
68
  /// @param l 节点t的左边界
69
  /// @param r 节点t的右边界
70
  void Build(int t, int l, int r)
71
  {
72
    // 标记恢复默认
73
    sum[t] = 0;
74
    add[t] = 0;
75
    mul[t] = 1;
76
    // 当节点t是底层节点时，记录sum值
77
    if (l == r)
78
    {
79
      sum[t] = a[l];
80
      return;
81
    }
82
    // 向下递归
83
    int mid = (l + r) / 2;
84
    Build(t * 2, l, mid);
85
    Build(t * 2 + 1, mid + 1, r);
86
    // 结算结果
87
    pushup(t, l, r);
88
  }
89

90
  /// @brief 对于节点t，在[x,y]的范围内增加k
91
  /// @param t 目标节点
92
  /// @param l 节点t的左边界
93
  /// @param r 节点t的右边界
94
  /// @param x 如brief
95
  /// @param y 如brief
96
  /// @param k 如brief
97
  void Add(int t, int l, int r, int x, int y, int k)
98
  {
99
    // 清空自己身上的标记
100
    pushdown(t, l, r);
101
    // 当节点t完全包含在[x,y]中时
102
    if (l >= x && r <= y)
103
    {
104
      // 对节点t进行add操作
105
      add[t] += k;
106
      sum[t] += k * (r - l + 1);
107
      return;
108
    }
109
    // 如果搭不上边，那么就不处理
110
    if (l > y || r < x)
111
    {
112
      return;
113
    }
114
    // 递归向下处理
115
    int mid = (l + r) / 2;
116
    Add(t * 2, l, mid, x, y, k);
117
    Add(t * 2 + 1, mid + 1, r, x, y, k);
118
    // 结算结果
119
    pushup(t, l, r);
120
  }
121

122
  /// @brief 对于节点t，在[x,y]的范围内的每个数都乘上k
123
  /// @param t 目标节点
124
  /// @param l 节点t的左边界
125
  /// @param r 节点t的右边界
126
  /// @param x 如brief
127
  /// @param y 如brief
128
  /// @param k 如brief
129
  void Mul(int t, int l, int r, int x, int y, int k)
130
  {
131
    // 清空自己身上的标记
132
    pushdown(t, l, r);
133
    // 当节点t完全包含在[x,y]中时
134
    if (l >= x && r <= y)
135
    {
136
      // 对节点t进行add操作
137
      mul[t] *= k;
138
      add[t] *= k; // 可省略
139
      sum[t] *= k;
140
      return;
141
    }
142
    // 如果搭不上边，那么就不处理
143
    if (l > y || r < x)
144
    {
145
      return;
146
    }
147
    // 递归向下处理
148
    int mid = (l + r) / 2;
149
    Mul(t * 2, l, mid, x, y, k);
150
    Mul(t * 2 + 1, mid + 1, r, x, y, k);
151
    // 结算结果
152
    pushup(t, l, r);
153
  }
154

155
  /// @brief 对于节点t，得到在[x,y]的范围内的每个数的和
156
  /// @param t 目标节点
157
  /// @param l 节点t的左边界
158
  /// @param r 节点t的右边界
159
  /// @param x 如brief
160
  /// @param y 如brief
161
  int Query(int t, int l, int r, int x, int y)
162
  {
163
    // 清空自己身上的标记
164
    pushdown(t, l, r);
165
    // 当节点t完全包含在[x,y]中时
166
    if (l >= x && r <= y)
167
    {
168
      // 计数
169
      return sum[t];
170
    }
171
    // 如果搭不上边，那么就记0
172
    if (l > y || r < x)
173
    {
174
      return 0;
175
    }
176
    // 递归向下处理
177
    int mid = (l + r) / 2;
178
    return Query(t * 2, l, mid, x, y) + Query(t * 2 + 1, mid + 1, r, x, y);
179
  }
180
};
181

182
int main()
183
{
184
  cin >> n >> q >> m;
185
  for (int i = 1; i <= n; i++)
186
  {
187
    cin >> a[i];
188
  }
189

190
  SegTree st;
191

192
  st.Build(1, 1, n);
193

194
  for (int i = 1; i <= q; i++)
195
  {
196
    int op;
197
    int x, y, k;
198
    cin >> op;
199
    switch (op)
200
    {
201
    case 1:
202
      cin >> x >> y >> k;
203
      st.Mul(1, 1, n, x, y, k);
204
      break;
205

206
    case 2:
207
      cin >> x >> y >> k;
208
      st.Add(1, 1, n, x, y, k);
209
      break;
210

211
    default:
212
      cin >> x >> y;
213
      cout << st.Query(1, 1, n, x, y) << endl;
214
      break;
215
    }
216
  }
217

218
  return 0;
219
}

复杂线段树——辅助标记的添加与应用#

题目：P2572 序列操作

题目描述#

lxhgww 最近收到了一个 $01$ 序列，序列里面包含了 $n$ 个数，下标从 $0$ 开始．这些数要么是 $0$ ，要么是 $1$ ，现在对于这个序列有五种变换操作和询问操作：

0 l r 把 $[l, r]$ 区间内的所有数全变成 $0$ ；
1 l r 把 $[l, r]$ 区间内的所有数全变成 $1$ ；
2 l r 把 $[l,r]$ 区间内的所有数全部取反，也就是说把所有的 $0$ 变成 $1$ ，把所有的 $1$ 变成 $0$ ；
3 l r 询问 $[l, r]$ 区间内总共有多少个 $1$ ；
4 l r 询问 $[l, r]$ 区间内最多有多少个连续的 $1$ ．

对于每一种询问操作，lxhgww 都需要给出回答，聪明的程序员们，你们能帮助他吗？

输入格式#

第一行两个正整数 $n,m$ ，表示序列长度与操作个数．

第二行包括 $n$ 个数，表示序列的初始状态．

接下来 $m$ 行，每行三个整数，表示一次操作．

输出格式#

对于每一个询问操作，输出一行一个数，表示其对应的答案．

数据范围#

对于 $100\%$ 的数据， $1\le n,m \le 10^5$ ．

我们想要实现对于每一种修改，每一种查询都能进行变化．

对于覆盖，两种查询都很好求，但对于取反，第二种查询就比较复杂．

首先，为了计算出区间内连续 1 的个数，我们需要知道其子区间从左边开始数的连续的 1 的数量lv1 以及从右边开始数的连续的 1 的数量rv1，那么，其区间内连续 1 的个数 con1 的转换公式为 $fa.con1 = max(left.con1, right.con1, left.rv1 + right.lv1)$ ，其中节点 $fa$ 的左右子节点分别为 $left$ 和 $right$ ．

但是，对于 lv1 和 rv1，甚至 con1，也很难知道其取反后的结果，所以，我们为这两个辅助标记再定义辅助标记，我们需要知道其子区间从左边开始数的连续的 0 的数量lv0、从右边开始数的连续的 0 的数量rv0 以及区间内 0 的个数con0，所以，对于一次取反操作，我们只需要分别交 lv1 和 rv1，lv0 和 rv0，con1 和 con0 就可以了．

对于这么多的标记，我们可以定义一个结构体来进行储存，并且重载 + 运算符来表示合并．

最后，我们只需要修改 pushdown、pushup 以及所有的改动函数来初始化和维护这些变量就可以了．

标程#

1
#include <bits/stdc++.h>
2

3
using namespace std;
4

5
const int N = 1e5 + 100;
6

7
struct Node
8
{
9
  // 修改标记（懒标记）
10
  bool rev;  // 是否取反
11
  int cover; // 覆盖成何值
12
  bool need; // 是否需要覆盖
13

14
  // 查询标记
15
  int sum;  // 记录当前区间内1的数量
16
  int len;  // 记录当前区间的长度
17
  int con1; // 记录当前最长的连续的一段1
18
  int con0; // 记录当前最长的连续的一段0
19
  int lv1;  // 记录从左边开始数的连续的1的数量
20
  int rv1;  // 记录从右边开始数的连续的1的数量
21
  int lv0;  // 记录从左边开始数的连续的0的数量
22
  int rv0;  // 记录从右边开始数的连续的0的数量
23
  friend Node operator+(Node a, Node b)
24
  {
25
    Node c;
26
    c.len = a.len + b.len;
27
    c.sum = a.sum + b.sum;
28
    c.con1 = max(max(a.con1, b.con1), a.rv1 + b.lv1);
29
    c.con0 = max(max(a.con0, b.con0), a.rv0 + b.lv0);
30
    c.lv1 = (a.sum == a.len) ? a.len + b.lv1 : a.lv1;
31
    c.lv0 = (a.sum == 0) ? a.len + b.lv0 : a.lv0;
32
    c.rv1 = (b.sum == b.len) ? b.len + a.rv1 : b.rv1;
33
    c.rv0 = (b.sum == 0) ? b.len + a.rv0 : b.rv0;
34
    return c;
35
  }
36
};
37

38
Node node[N * 4]; // 线段树节点数组，4倍空间足够维护区间
39

40
struct SegTree
41
{
42
  // pushup: 合并左右儿子的区间信息，更新父节点
43
  void pushup(int t, int l, int r)
44
  {
45
    // 先保存父节点的懒标记（need/cover/rev），再合并左右儿子的区间信息
46
    Node c = node[t];
47
    node[t] = node[t * 2] + node[t * 2 + 1]; // 区间合并
48
    node[t].need = c.need;
49
    node[t].cover = c.cover;
50
    node[t].rev = c.rev;
51
  }
52

53
  // hcover: 把节点t的区间全部赋成v（0或1），并设置懒标记
54
  void hcover(int t, int v)
55
  {
56
    node[t].need = true; // 标记该区间需要被覆盖
57
    node[t].cover = v;   // 记录要覆盖成的值
58
    node[t].rev = 0;   // 覆盖后不再需要取反
59
    // 直接更新区间信息
60
    node[t].sum = node[t].len * v;
61
    node[t].con1 = node[t].len * v;
62
    node[t].con0 = node[t].len * !v;
63
    node[t].lv1 = node[t].len * v;
64
    node[t].lv0 = node[t].len * !v;
65
    node[t].rv1 = node[t].len * v;
66
    node[t].rv0 = node[t].len * !v;
67
  }
68

69
  // hrev: 把节点t的区间全部取反，并设置懒标记
70
  void hrev(int t)
71
  {
72
    node[t].rev = !node[t].rev;         // 取反标记异或
73
    node[t].sum = node[t].len - node[t].sum; // 1变0，0变1
74
    swap(node[t].con1, node[t].con0);     // 连续1和连续0交换
75
    swap(node[t].lv1, node[t].lv0);
76
    swap(node[t].rv1, node[t].rv0);
77
  }
78

79
  // pushdown: 下传懒标记，将父节点的标记传递给左右儿子
80
  void pushdown(int t, int l, int r)
81
  {
82
    if (l == r)
83
      return; // 叶子节点无需下传
84
    // 如果有区间赋值标记，优先下传
85
    if (node[t].need)
86
    {
87
      hcover(t * 2, node[t].cover);
88
      hcover(t * 2 + 1, node[t].cover);
89
      node[t].need = false;
90
      node[t].cover = 0;
91
    }
92
    // 如果有区间取反标记，下传
93
    if (node[t].rev)
94
    {
95
      hrev(t * 2);
96
      hrev(t * 2 + 1);
97
      node[t].rev = 0;
98
    }
99
  }
100

101
  // Build: 建树，递归初始化每个节点的区间信息
102
  void Build(int t, int l, int r, int *v)
103
  {
104
    if (l == r)
105
    {
106
      // 叶子节点，直接赋值
107
      node[t].need = false;
108
      node[t].cover = 0;
109
      node[t].rev = 0;
110
      node[t].len = 1;
111
      node[t].sum = v[l];
112
      node[t].con1 = v[l];
113
      node[t].con0 = !v[l];
114
      node[t].lv1 = v[l];
115
      node[t].lv0 = !v[l];
116
      node[t].rv1 = v[l];
117
      node[t].rv0 = !v[l];
118
      return;
119
    }
120
    int mid = (l + r) / 2;
121
    Build(t * 2, l, mid, v);
122
    Build(t * 2 + 1, mid + 1, r, v);
123
    pushup(t, l, r);
124
  }
125

126
  // 区间赋值操作：将[x, y]区间全部赋成k（0或1）
127
  void Cover(int t, int l, int r, int x, int y, int k)
128
  {
129
    pushdown(t, l, r); // 递归前先下传懒标记
130
    if (x <= l && r <= y)
131
    {
132
      hcover(t, k); // 完全覆盖，直接赋值
133
      return;
134
    }
135
    if (y < l || r < x)
136
      return; // 无交集，直接返回
137
    int mid = (l + r) / 2;
138
    Cover(t * 2, l, mid, x, y, k);
139
    Cover(t * 2 + 1, mid + 1, r, x, y, k);
140
    pushup(t, l, r); // 回溯时合并区间信息
141
  }
142

143
  // 区间取反操作：将[x, y]区间全部取反
144
  void Rev(int t, int l, int r, int x, int y)
145
  {
146
    pushdown(t, l, r); // 递归前先下传懒标记
147
    if (x <= l && r <= y)
148
    {
149
      hrev(t); // 完全覆盖，直接取反
150
      return;
151
    }
152
    if (y < l || r < x)
153
      return; // 无交集，直接返回
154
    int mid = (l + r) / 2;
155
    Rev(t * 2, l, mid, x, y);
156
    Rev(t * 2 + 1, mid + 1, r, x, y);
157
    pushup(t, l, r); // 回溯时合并区间信息
158
  }
159

160
  // 区间查询：返回[x, y]区间的信息
161
  Node Query(int t, int l, int r, int x, int y)
162
  {
163
    pushdown(t, l, r); // 递归前先下传懒标记
164
    if (x <= l && r <= y)
165
      return node[t]; // 完全覆盖，直接返回
166
    int mid = (l + r) / 2;
167
    if (y <= mid)
168
      return Query(t * 2, l, mid, x, y); // 只在左子树
169
    if (x > mid)
170
      return Query(t * 2 + 1, mid + 1, r, x, y); // 只在右子树
171
    // 跨越左右子树，合并结果
172
    Node q1 = Query(t * 2, l, mid, x, y);
173
    Node q2 = Query(t * 2 + 1, mid + 1, r, x, y);
174
    return q1 + q2;
175
  }
176
};
177

178
int a[N];
179

180
// 此处的read()是快读函数，可以极快速的读入一个整数
181
int read()
182
{
183
  int s = 0, c = getchar(), a = 0;
184
  while (!isdigit(c))
185
    s |= c == '-', c = getchar();
186
  while (isdigit(c))
187
    a = a * 10 + c - '0', c = getchar();
188
  return s ? -a : a;
189
}
190

191
int main()
192
{
193
  int n, m;
194
  // 读入序列长度n和操作次数m
195
  n = read(), m = read();
196
  SegTree tree;
197
  // 读入初始01序列，下标从1开始，a[1]~a[n]
198
  for (int i = 1; i <= n; ++i)
199
    a[i] = read();
200
  // 建树，根节点编号为1，维护区间[1, n]的信息
201
  tree.Build(1, 1, n, a);
202
  // 依次处理m个操作
203
  for (int i = 1; i <= m; ++i)
204
  {
205
    int op, l, r;
206
    // 读入操作类型op和区间[l, r]，题目输入下标从0开始，这里+1转为1开始
207
    op = read(), l = read() + 1, r = read() + 1;
208
    if (op == 0)
209
      // 区间[l, r]赋值为0
210
      tree.Cover(1, 1, n, l, r, 0);
211
    if (op == 1)
212
      // 区间[l, r]赋值为1
213
      tree.Cover(1, 1, n, l, r, 1);
214
    if (op == 2)
215
      // 区间[l, r]取反
216
      tree.Rev(1, 1, n, l, r);
217
    if (op == 3)
218
    {
219
      // 查询区间[l, r]内1的个数，输出结果
220
      Node res = tree.Query(1, 1, n, l, r);
221
      cout << res.sum << endl;
222
    }
223
    if (op == 4)
224
    {
225
      // 查询区间[l, r]内最长连续1的长度，输出结果
226
      Node res = tree.Query(1, 1, n, l, r);
227
      cout << res.con1 << endl;
228
    }
229
  }
230
  return 0;
231
}

音乐

音乐