题解 | #小红的01子序列构造（easy）#

D 小红的01子序列构造（easy）

两种写法，这里都介绍一下：

方法1:双指针

先考虑一个区间内的 $01$ 子序列如何统计，我们只需要对于每个 $1$ ，看它之前有几个 $0$ ，就是它的贡献。

例如对于序列 $00101101$ ， $s_2, s_4, s_5,s_7$ 都是 $1$ ，他们的贡献依次为 $2, 3, 3, 4$ ，所以最后的 $01$ 子序列数为 $12$ 。

用双指针枚举区间的左右端点，假设当前区间是 $[l, r]$ ，区间内的 $01$ 子序列为 $x$ 个。

如果 $x = k$ 则直接输出当前区间。

如果 $x > k$ 说明当前 $01$ 子序列过多，需要把左端点往右靠。

如果把 $0$ 给排出序列，说明后面的所有 $1$ 的贡献都减少了 $1$ ，所以总共减少了 $cnt_1$ 个（ $cnt_1$ 表示当前区间内 $1$ 的个数）
如果把 $1$ 给排出序列，对个数毫无影响

如果 $x < k$ 说明当前 $01$ 子序列过少，需要把右端点往右扩展。

如果加进来一个 $0$ ，对答案毫无影响，但是 $cnt_0$ 需要加 $1$
如果加进来一个 $1$ ，之前的 $1$ 贡献无影响，新加进来的 $1$ 贡献为 $cnt_0$

时间复杂度 $O(n)$

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

int main() {
    LL n, k;
    cin >> n >> k;
    string s; cin >> s;
    int cnt0 = 0, cnt1 = 0;
    int l = 0, r = 0;
    if (s[0] == '0') cnt0 ++;
    if (s[0] == '1') cnt1 ++;
    LL num = 0;
    while (l < n && r < n) {
        if (num == k) {
            cout << l + 1 << ' ' << r + 1 << endl;
            return 0;
        }
        if (num < k) {
            r ++;
            if (s[r] == '0') cnt0 ++;
            else {
                num += cnt0;
                cnt1 ++;
            }
        } else {
            if (s[l] == '0') {
                num -= cnt1;
                cnt0 --;
            } else cnt1 --;
            l ++;
        }
    }
    cout << -1 << endl;
    return 0;
}

方法2:前缀和+二分

我们思考下如何快速算出一段指定区间 $[l, r]$ 的贡献。

经过上面的过程，我们可以看出贡献只由区间内的 $1$ 产生，每个 $1$ 产生的贡献就是它们之前的 $0$ 的个数。所以我们需要求一段区间内的 $0$ 的个数，这个可以由前缀和实现。我们也可以预处理出每个 $1$ 的贡献，然后计算出区间内的贡献和即可。这个也可以由前缀和实现。

具体来说，我们可以定义几个前缀和数组

令 $pre_{0, i}$ 为前 $i$ 个数中 $0$ 的个数
令 $pre_{1, i}$ 为前 $i$ 个数中 $1$ 的个数
令 $sum_i$ 为区间 $[1, i]$ 的贡献

所以，对于区间 $[l, r]$ 来说，总贡献就是 $sum_r - sum_{l-1} - pre_{0, l-1} \cdot (pre_{1, r}-pre_{1,l-1})$

例如对于 $000101101$ 来说，它们每个数的贡献就是 $0,0,0,3,0,4,4,0,5$ ，对应的前缀和数组就是 $0,0,0,3,3,7,11,11,16$ 。

假设我们要求 $[3, 9]$ 的贡献，可能同学们会诈以为是 $sum_9-sum_2$ ，但是这样的话我们没有想到前面少的两个0对后面1的影响，我们来看看少了多少。

如果前面两个0没了，那么后面的贡献会变成 $0,0,0,1,0,2,2,0,3$ ，对应的前缀和数组变成了 $0,0,0,1,1,3,5,5,8$ 。前面每少掉一个 $0$ ，后面的所有 $1$ 的贡献都少了 $1$ 。所以少掉的贡献就是 $pre_{0, l-1} \cdot (pre_{1, r}-pre_{1,l-1})$ ，所以正确的贡献应该是原来区间和的基础上，减去少掉的贡献，即 $sum_r - sum_{l-1} - pre_{0, l-1} \cdot (pre_{1, r}-pre_{1,l-1})$

那么也简单了，我们可以枚举区间左端点，然后二分找出贡献大于等于 $k$ 的最小贡献值，看看是不是刚好等于 $k$ 即可。时间复杂度 $O(n \log n)$

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
int pre0[N], pre1[N];
LL sum[N];

LL calc(int l, int r) {
    return sum[r] - sum[l - 1] - 1ll * pre0[l - 1] * (pre1[r] - pre1[l - 1]);
}

int main() {
    LL n, k;
    cin >> n >> k;
    string s; cin >> s;
    for (int i = 1; i <= n; i ++ ) {
        pre0[i] = pre0[i - 1];
        pre1[i] = pre1[i - 1];
        if (s[i - 1] == '0') pre0[i] ++;
        if (s[i - 1] == '1') pre1[i] ++;
    }
    for (int i = 1; i <= n; i ++ ) {
        sum[i] = sum[i - 1];
        if (s[i - 1] == '1') sum[i] += pre0[i];
    }
    for (int i = 1; i <= n; i ++ ) {
        int l = i, r = n;
        // 二分查找i开头，贡献大于等于k个区间的最小贡献
        int ans = -1;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (calc(i, mid) >= k) {
                ans = mid;
                r = mid - 1;
            } else l = mid + 1;
        }
        if (ans == -1) break;
        if (calc(i, ans) == k) {
            cout << i << ' ' << ans << endl;
            return 0;
        }
    }
    cout << -1 << endl;
    return 0;
}