[SCOI2010] 序列操作

题目链接

洛谷

题目分析

warning

本题可能需要亿点耐心

题目要求支持五个操作

  1. 区间填充为 0
  2. 区间填充为 1
  3. 区间取反
  4. 区间求和
  5. 求区间最多有多少个连续的 1

先忽略操作 5，对于操作 1-4，取反和填充设置两个 $ lazytag $，在操作时，如果另一类操作已经有了 $ lazytag $，就把另一类操作应用下去，先填充再取反。

操作 5 比较麻烦，先看下面这张图。

区间合并示意图
区间合并示意图

如图所示，区间 $ a $ 和 $ b $ 合并为区间 $ c $，红色的区域代表连续的 1，可以看到

\[ \begin{equation*} pre_c = pre_a \end{equation*} \] \[ \begin{equation*} suf_c = suf_b \end{equation*} \] \[ \begin{equation*} maxl_c = \max \{maxl_a,maxl_b,suf_a+pre_b\} \end{equation*} \]

关于 $ pre_c $ 和 $ suf_c $ ，可能并不止那么简单，因为 $ a $ 和 $ b $ 可能是全 1 序列，会导致贯通，还需要判断一下。

由于有取反操作，对于每个区间，我们不仅维护关于 1 的 $ pre $ 、$ sur $ 、$ maxl $ 三个数据，还要维护关于 0 的才能完成操作 5.

代码实现

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
#include <bits/stdc++.h>

using namespace std;

const int N = 100010;

struct Node {
    int l, r;
    int sum;
    int maxl1, pre1, suf1;
    int maxl0, pre0, suf0;
    int filltag;
    bool invertag;
} tree[N * 4];
int num[N];
int n, m;

inline int size(int x)
{
    return tree[x].r - tree[x].l + 1;
}

void merge(const Node& l, const Node& r, Node& ori)
{
    ori.sum = l.sum + r.sum;

    ori.pre1 = l.pre1;
    if (l.pre1 == l.r - l.l + 1) ori.pre1 += r.pre1;
    ori.suf1 = r.suf1;
    if (r.suf1 == r.r - r.l + 1) ori.suf1 += l.suf1;
    ori.maxl1 = max(max(l.maxl1, r.maxl1), l.suf1 + r.pre1);

    ori.pre0 = l.pre0;
    if (l.pre0 == l.r - l.l + 1) ori.pre0 += r.pre0;
    ori.suf0 = r.suf0;
    if (r.suf0 == r.r - r.l + 1) ori.suf0 += l.suf0;
    ori.maxl0 = max(max(l.maxl0, r.maxl0), l.suf0 + r.pre0);
}

inline void push_up(int x)
{
    merge(tree[x << 1], tree[x << 1 | 1], tree[x]);
}

inline void push_down(int x)
{
    if (tree[x].filltag == 1) {
        tree[x << 1].filltag = 1, tree[x << 1 | 1].filltag = 1;
        tree[x << 1].invertag = 0, tree[x << 1 | 1].invertag = 0;
        tree[x << 1].pre1 = tree[x << 1].suf1 = tree[x << 1].maxl1 = size(x << 1);
        tree[x << 1 | 1].pre1 = tree[x << 1 | 1].suf1 = tree[x << 1 | 1].maxl1 = size(x << 1 | 1);
        tree[x << 1].pre0 = tree[x << 1].suf0 = tree[x << 1].maxl0 = 0;
        tree[x << 1 | 1].pre0 = tree[x << 1 | 1].suf0 = tree[x << 1 | 1].maxl0 = 0;
        tree[x << 1].sum = size(x << 1);
        tree[x << 1 | 1].sum = size(x << 1 | 1);
        tree[x].filltag = -1;
    } else if (tree[x].filltag == 0) {
        tree[x << 1].filltag = 0, tree[x << 1 | 1].filltag = 0;
        tree[x << 1].invertag = 0, tree[x << 1 | 1].invertag = 0;
        tree[x << 1].pre1 = tree[x << 1].suf1 = tree[x << 1].maxl1 = 0;
        tree[x << 1 | 1].pre1 = tree[x << 1 | 1].suf1 = tree[x << 1 | 1].maxl1 = 0;
        tree[x << 1].pre0 = tree[x << 1].suf0 = tree[x << 1].maxl0 = size(x << 1);
        tree[x << 1 | 1].pre0 = tree[x << 1 | 1].suf0 = tree[x << 1 | 1].maxl0 = size(x << 1 | 1);
        tree[x << 1].sum = 0;
        tree[x << 1 | 1].sum = 0;
        tree[x].filltag = -1;
    }
    if (tree[x].invertag) {
        if (tree[x << 1].filltag != -1) push_down(x << 1);
        if (tree[x << 1 | 1].filltag != -1) push_down(x << 1 | 1);
        swap(tree[x << 1].maxl0, tree[x << 1].maxl1);
        swap(tree[x << 1 | 1].maxl0, tree[x << 1 | 1].maxl1);
        swap(tree[x << 1].pre0, tree[x << 1].pre1);
        swap(tree[x << 1 | 1].pre0, tree[x << 1 | 1].pre1);
        swap(tree[x << 1].suf0, tree[x << 1].suf1);
        swap(tree[x << 1 | 1].suf0, tree[x << 1 | 1].suf1);
        tree[x << 1].invertag = !tree[x << 1].invertag;
        tree[x << 1 | 1].invertag = !tree[x << 1 | 1].invertag;
        tree[x << 1].sum = size(x << 1) - tree[x << 1].sum;
        tree[x << 1 | 1].sum = size(x << 1 | 1) - tree[x << 1 | 1].sum;
        tree[x].invertag = 0;
    }
}

void build(int x, int l, int r)
{
    tree[x].l = l, tree[x].r = r;
    tree[x].filltag = -1, tree[x].invertag = 0;
    if (l == r) {
        tree[x].sum = num[l];
        tree[x].pre1 = num[l];
        tree[x].suf1 = num[l];
        tree[x].maxl1 = num[l];
        tree[x].pre0 = !num[l];
        tree[x].suf0 = !num[l];
        tree[x].maxl0 = !num[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(x << 1, l, mid);
    build(x << 1 | 1, mid + 1, r);
    push_up(x);
}

// 1 的总和
int sum(int x, int l, int r)
{
    if (tree[x].l > r || tree[x].r < l) {
        return 0;
    }
    if (tree[x].l >= l && tree[x].r <= r) {
        return tree[x].sum;
    }
    push_down(x);
    int ans = 0;
    if (tree[x << 1].r >= l) ans += sum(x << 1, l, r);
    if (tree[x << 1 | 1].l <= r) ans += sum(x << 1 | 1, l, r);
    return ans;
}

// 全覆盖为 0
void zero_fill(int x, int l, int r)
{
    if (tree[x].l > r || tree[x].r < l) {
        return;
    }
    if (tree[x].l >= l && tree[x].r <= r) {
        push_down(x);
        tree[x].filltag = 0;
        tree[x].sum = 0;
        tree[x].pre1 = tree[x].suf1 = tree[x].maxl1 = 0;
        tree[x].pre0 = tree[x].suf0 = tree[x].maxl0 = size(x);
        return;
    }
    push_down(x);
    if (tree[x << 1].r >= l) zero_fill(x << 1, l, r);
    if (tree[x << 1 | 1].l <= r) zero_fill(x << 1 | 1, l, r);
    push_up(x);
}

// 全覆盖为 1
void one_fill(int x, int l, int r)
{
    if (tree[x].l > r || tree[x].r < l) {
        return;
    }
    if (tree[x].l >= l && tree[x].r <= r) {
        push_down(x);
        tree[x].filltag = 1;
        tree[x].sum = size(x);
        tree[x].pre1 = tree[x].suf1 = tree[x].maxl1 = size(x);
        tree[x].pre0 = tree[x].suf0 = tree[x].maxl0 = 0;
        return;
    }
    push_down(x);
    if (tree[x << 1].r >= l) one_fill(x << 1, l, r);
    if (tree[x << 1 | 1].l <= r) one_fill(x << 1 | 1, l, r);
    push_up(x);
}

// 取反
void inverse(int x, int l, int r)
{
    if (tree[x].l > r || tree[x].r < l) {
        return;
    }
    if (tree[x].l >= l && tree[x].r <= r) {
        push_down(x);
        tree[x].invertag = !tree[x].invertag;// 没取反就记取反，两次取反等于不取反
        tree[x].sum = size(x) - tree[x].sum;
        swap(tree[x].maxl0, tree[x].maxl1);
        swap(tree[x].pre0, tree[x].pre1);
        swap(tree[x].suf0, tree[x].suf1);
        return;
    }
    push_down(x);
    if (tree[x << 1].r >= l) inverse(x << 1, l, r);
    if (tree[x << 1 | 1].l <= r) inverse(x << 1 | 1, l, r);
    push_up(x);
}

// 查找最长的连续的 1
Node query(int x, int l, int r)
{
    if (tree[x].l > r || tree[x].r < l) {
        return {};
    }
    if (tree[x].l >= l && tree[x].r <= r) {
        return tree[x];
    }
    push_down(x);
    Node a{}, b{}, ans{};
    if (tree[x << 1].r >= l) a = query(x << 1, l, r);
    if (tree[x << 1 | 1].l <= r) b = query(x << 1 | 1, l, r);

    merge(a, b, ans);
    return ans;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> num[i];
    }
    build(1, 1, n);

    for (int i = 1; i <= m; i++) {
        int op, l, r;
        cin >> op >> l >> r;
        l++, r++;
        switch (op) {
        case 0: {
            zero_fill(1, l, r);
            break;
        }
        case 1: {
            one_fill(1, l, r);
            break;
        }
        case 2: {
            inverse(1, l, r);
            break;
        }
        case 3: {
            cout << sum(1, l, r) << endl;
            break;
        }
        case 4: {
            cout << query(1, l, r).maxl1 << endl;
            break;
        }
        }
    }
    return 0;
}
题解
#题解 #省选 #OI #线段树
[SCOI2010] 序列操作
http://hghgthifg.github.io/2023/08/27/solution/SCOI2010-序列操作/
作者
小H
发布于
2023年8月27日
许可协议