ABC381 C-E题解

C - 11/22 Substring

枚举每个 /，从 / 出发向左右两边扩展到最远。因为每个点最多能被访问一次（向右只扩展 2，向左只扩展 1），复杂度为 \(O(n)\)。

int ans = 0;
for (int i = 0; i < n; i++) {
    if (s[i] != '/') continue;
    int l = i - 1, r = i + 1, len = 1;
    while (l >= 0 && r < n && s[l] == '1' && s[r] == '2')
        len += 2, l--, r++;
    ans = max(ans, len);
}
cout << ans << '\n';

D - 1122 Substring

考虑从头开始遍历，如果当前 \(a_i\neq a_{i+1}\) 则跳过（每次往后走一步），\(a_i=a_{i+1}\) 则开始记录（每次往后走两步），直到 不相等 或者 出现了重复的数字。如果是前者，统计答案，清空长度即可。对于后者，需要开一个 unordered_map 记录当前 1122 数列里每个数字出现的位置。一旦重复，就更新答案，然后把当前 1122 数列的开头 \(st\) 到重复数字第一次出现的位置 \(ed\) 中间的数字全部扔掉，\(st\gets ed+2\) 继续向后找。因为每个数字最多被扔掉一次，所以复杂度仍为 \(O(n)\)。

但是发现这个算法没法处理 11122 这种情况，它注意不到 1122 的部分，而是在 1112 失配之后直接跳到 22 了。想到我们可以按开头位置的奇偶性分开处理。强制开头为奇数跑一遍，强制开头为偶数跑一遍，最后答案取最大值即可。

int ans = 0;
auto startFrom = [&](int x) {
    int st = -1;
    map<int, int> mp;
    for (int i = x; i < n; i += 2) {
        if (i == n - 1 || a[i] != a[i + 1]) { // 如果i=n-1则肯定失配
            if (st != -1) {
                ans = max(ans, i - st);
                st = -1;
                mp.clear();
            }
            continue;
        }
        if (st == -1) st = i;
        if (mp.count(a[i])) {
            ans = max(ans, i - st);
            int ed = mp[a[i]];
            for (int j = st; j <= ed; j += 2)
                mp.erase(a[j]); // 清除st~ed之间的数
            st = ed + 2;
        }
        mp[a[i]] = i;
    }
    if (st != -1) ans = max(ans, n - st);
};
startFrom(0), startFrom(1);
cout << ans << '\n';

E - 11/22 Subsequence

朴素的想法是枚举每个区间中的 /，用前缀和计算它前面的 1 的个数 \(cnt_1\) 和后面的 2 的个数 \(cnt_2\)，用 \(\min(cnt_1,cnt_2)\) 更新答案，但枚举 / 是 \(O(n)\) 的，复杂度过高。

注意到从前到后枚举区间内 / 的过程中，\(cnt_1\) 单调增加，\(cnt_2\) 单调减少，\(\min(cnt_1,cnt_2)\) 的最大值一定取在 \(cnt1<cnt_2\) 到 \(cnt_1>cnt_2\) 的交界处（之前 \(cnt_1\) 是最小值，不断增大；之后 \(cnt_2\) 是最小值，不断减小）。这个过程是有单调性的，可以二分，复杂度为 \(O(q\log n)\)。

int n, q;
std::string s;
std::cin >> n >> q >> s;
std::array<std::vector<int>, 2> cnt{std::vector<int>(n), std::vector<int>(n)}; // 12前缀和
std::vector<int> pos; // 记录/的位置
for (int i = 0; i < n; i++) {
    s[i] == '/' ? pos.emplace_back(i) : cnt[s[i] - '1'][i]++;
}
std::partial_sum(cnt[0].begin(), cnt[0].end(), cnt[0].begin()); // 自动前缀和
std::partial_sum(cnt[1].begin(), cnt[1].end(), cnt[1].begin());
auto getSum = [&](int i, int l, int r) {
    return cnt[i][r] - (l ? cnt[i][l - 1] : 0);
};
auto calc = [&](int l, int r) -> int {
    int L = std::lower_bound(pos.begin(), pos.end(), l) - pos.begin(); // 区间内第一个/
    int R = std::upper_bound(pos.begin(), pos.end(), r) - pos.begin() - 1; // upper_bound求出大于r的第一个/，-1得到区间内的最后一个/
    if (R < L) return 0; // 区间内没有/
    int i = *std::ranges::partition_point(std::ranges::iota_view(L, R), [&](int x) -> bool {
        return getSum(0, l, pos[x]) <= getSum(1, pos[x], r);
    }); // 二分，找到第一个cnt1>cnt2的位置
    int res = 0; // min(cnt1,cnt2)的最大值
    if (i <= R) res = std::max(res, std::min(getSum(0, l, pos[i]), getSum(1, pos[i], r)));
    if (i >= L + 1) res = std::max(res, std::min(getSum(0, l, pos[i - 1]), getSum(1, pos[i - 1], r))); // 也可能在最后一个cnt1<=cnt2的位置上取得，峰的位置不一定在哪边
    return res * 2 + 1;
};
for (int l, r; q--;) {
    std::cin >> l >> r;
    std::cout << calc(l - 1, r - 1) << '\n';
}

因为有大小相等的点，不能三分。