[JRKSJ R2] 01 序列

题意

给定一个只含 0/1 的序列，回答两类区间询问：

1 l r：求 a[l..r] 的最长不下降子序列长度
2 l r：求 a[l..r] 的最长上升子序列长度

数据范围非常大，n 到 10^6，询问次数到 5 * 10^6，所以每次询问必须非常快。

思路

先看一个可以直接验证想法的朴素解：

cpp

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

const int MAXN = 205;

int n, m;
int a[MAXN];

int solve_non_decreasing(int l, int r) {
    int answer = 0;

    // 枚举分界点 k：取左边全部 0，右边全部 1。
    for (int k = l - 1; k <= r; k++) {
        int cnt0 = 0;
        int cnt1 = 0;
        for (int i = l; i <= k; i++) {
            if (a[i] == 0) {
                cnt0++;
            }
        }
        for (int i = k + 1; i <= r; i++) {
            if (a[i] == 1) {
                cnt1++;
            }
        }
        answer = max(answer, cnt0 + cnt1);
    }

    return answer;
}

int solve_increasing(int l, int r) {
    int answer = 1;

    for (int i = l; i <= r; i++) {
        for (int j = i + 1; j <= r; j++) {
            if (a[i] < a[j]) {
                answer = 2;
            }
        }
    }

    return answer;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

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

    while (m--) {
        int op, l, r;
        cin >> op >> l >> r;

        if (op == 1) {
            cout << solve_non_decreasing(l, r) << '\n';
        }
        else {
            cout << solve_increasing(l, r) << '\n';
        }
    }

    return 0;
}

如果直接在每个区间里做 LIS，哪怕只利用 01 串的特殊性，也还是太慢。

1. 最长不下降子序列

在 01 串里，不下降子序列只能长成：

text

1若干个 0 + 若干个 1

所以只要枚举一个分界点 k：

从 l..k 里取所有 0
从 k+1..r 里取所有 1

答案就是：

text

1max( [l..k] 中 0 的个数 + [k+1..r] 中 1 的个数 )

设 pre[i] 表示前 i 个数里 1 的个数，那么：

[l..k] 中 0 的个数是 (k-l+1) - (pre[k]-pre[l-1])
[k+1..r] 中 1 的个数是 pre[r] - pre[k]

两项相加后得到：

text

1pre[l-1] + pre[r] - l + 1 + (k - 2 * pre[k])

对于一次询问，前面那一大段是常数，所以问题就变成：

text

1在区间 [l-1, r] 中求 max( k - 2 * pre[k] )

这是静态区间最大值，直接用 ST 表维护即可。

2. 最长上升子序列

严格上升的 01 子序列只能是：

text

10, 1

所以答案只可能是：

2：区间里存在一个 0 出现在某个 1 的前面
1：否则只能取单个元素

于是只要预处理：

next_zero[i]：从 i 开始往后第一个 0 的位置
prev_one[i]：到 i 为止最后一个 1 的位置

对于区间 [l, r]，如果 next_zero[l] < prev_one[r]，说明确实存在 0 在 1 前面，答案就是 2；否则答案是 1。

这两个查询都能做到 $O(1)$ 。

代码

cpp

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

const int MAXN = 1000005;
const int MAXLOG = 21;
const int BUF_SIZE = 1 << 20;

int n, m;
unsigned char a[MAXN];
int pre_one[MAXN];
int lg2_table[MAXN];
int f[MAXN];                   // f[i] = i - 2 * 前 i 个 1 的个数
int st[MAXLOG][MAXN];          // 区间最大值 ST 表，维护 f
int next_zero[MAXN];
int prev_one_pos[MAXN];
char outbuf[BUF_SIZE];
int outpos = 0;

namespace FastIO {
char inbuf[BUF_SIZE];
int inpos = 0;
int inlen = 0;

inline int gc() {
    if (inpos == inlen) {
        inlen = fread(inbuf, 1, BUF_SIZE, stdin);
        inpos = 0;
        if (inlen == 0) {
            return EOF;
        }
    }
    return inbuf[inpos++];
}

template <typename T>
inline void read(T &x) {
    x = 0;
    int sign = 1;
    int c = gc();
    while (c != '-' && (c < '0' || c > '9')) {
        c = gc();
    }
    if (c == '-') {
        sign = -1;
        c = gc();
    }
    while (c >= '0' && c <= '9') {
        x = x * 10 + c - '0';
        c = gc();
    }
    x *= sign;
}
}

inline void flush_output() {
    fwrite(outbuf, 1, outpos, stdout);
    outpos = 0;
}

inline void put_char(int c) {
    if (outpos == BUF_SIZE) {
        flush_output();
    }
    outbuf[outpos++] = (char)c;
}

inline void write_int(int x) {
    if (x == 0) {
        put_char('0');
        put_char('\n');
        return;
    }
    if (x < 0) {
        put_char('-');
        x = -x;
    }
    char s[20];
    int len = 0;
    while (x > 0) {
        s[len++] = (char)('0' + x % 10);
        x /= 10;
    }
    for (int i = len - 1; i >= 0; i--) {
        put_char(s[i]);
    }
    put_char('\n');
}

void build_logs() {
    lg2_table[1] = 0;
    for (int i = 2; i <= n + 1; i++) {
        lg2_table[i] = lg2_table[i >> 1] + 1;
    }
}

void build_sparse_table() {
    for (int i = 0; i <= n; i++) {
        st[0][i] = f[i];
    }

    for (int k = 1; k < MAXLOG; k++) {
        int len = 1 << k;
        int half = len >> 1;
        if (len > n + 1) {
            break;
        }
        for (int i = 0; i + len - 1 <= n; i++) {
            st[k][i] = max(st[k - 1][i], st[k - 1][i + half]);
        }
    }
}

inline int query_max(int l, int r) {
    int k = lg2_table[r - l + 1];
    return max(st[k][l], st[k][r - (1 << k) + 1]);
}

inline int solve_non_decreasing(int l, int r) {
    // 枚举“0 段”和“1 段”的分界点 k：
    // 取 [l, k] 中所有 0，再取 [k+1, r] 中所有 1。
    int best = query_max(l - 1, r);
    return pre_one[l - 1] + pre_one[r] - l + 1 + best;
}

inline int solve_increasing(int l, int r) {
    // 01 串的严格上升子序列只可能是 0,1，长度最多为 2。
    // 只要区间里存在一个 0 在某个 1 前面，答案就是 2，否则是 1。
    if (next_zero[l] < prev_one_pos[r]) {
        return 2;
    }
    return 1;
}

int main() {
    FastIO::read(n);
    FastIO::read(m);

    pre_one[0] = 0;
    prev_one_pos[0] = 0;
    for (int i = 1; i <= n; i++) {
        int x;
        FastIO::read(x);
        a[i] = (unsigned char)x;
        pre_one[i] = pre_one[i - 1] + x;
        prev_one_pos[i] = (x == 1 ? i : prev_one_pos[i - 1]);
    }

    next_zero[n + 1] = n + 1;
    for (int i = n; i >= 1; i--) {
        if (a[i] == 0) {
            next_zero[i] = i;
        }
        else {
            next_zero[i] = next_zero[i + 1];
        }
    }

    for (int i = 0; i <= n; i++) {
        f[i] = i - (pre_one[i] << 1);
    }

    build_logs();
    build_sparse_table();

    for (int i = 1; i <= m; i++) {
        int op, l, r;
        FastIO::read(op);
        FastIO::read(l);
        FastIO::read(r);

        if (op == 1) {
            write_int(solve_non_decreasing(l, r));
        }
        else {
            write_int(solve_increasing(l, r));
        }
    }

    flush_output();
    return 0;
}

复杂度

预处理前缀和、next_zero、prev_one： $O(n)$
建 ST 表： $O(n log n)$
每次询问： $O(1)$

总时间复杂度 $O(n log n + m)$ ，空间复杂度 $O(n log n)$ 。

总结

这题的关键不是套普通 LIS 模板，而是抓住 01 串的结构非常简单：

不下降子序列一定是“前面一段 0，后面一段 1”
严格上升子序列最多只有 0,1 两个数

把这两个性质用前缀和和位置预处理表达出来以后，问题就能压成常数时间查询。

$\text{Subtask}$	$n\le$	$m\le$	特殊性质	分值
$\text{1}$	$10^6$	$10^6$	所有 $a_i$ 均相等	$5$
$\text{2}$	$10^3$	$10^3$	无	$10$
$\text{3}$	$10^4$	$10^4$	无	$15$
$\text{4}$	$10^5$	$10^5$	无	$30$
$\text{5}$	$10^6$	$5\times10^6$	无	$40$
$\text{6}$	$10^6$	$5\times10^6$	hack 数据	$0$

目录

题意

思路

1. 最长不下降子序列

2. 最长上升子序列

代码

复杂度

总结