Codeforces Round 1024(Div. 2)D~F题解

比赛链接

D

通过观察规则不难看出所有奇数位置数字和所有偶数位置数字是不互通的。尝试按照规则构造最小字典序序列，可以发现前 $n-3$ 个数字可以通过贪心构造出最小字典序，也就是奇数位置从小到大排列，偶数位置从小到大排列，这样构造之后得到的字典序一定最小，但是规则是一对奇偶位置一起交换，所以需要判断这样构造出来的序列是否合法，如果不合法，应该如何修改。

首先将奇偶位置分离开来分别构造一个数组，然后每次操作会发现，对于奇偶位置操作是相同的，也就是说逆序对相对数量不会发生变化，所以我们不妨直接按照下标进行排序，这样初始奇偶数列的下标的逆序对数量就是0，最后统计排序好的下标的逆序对数量差必须是偶数即可。

i64 countInversions(std::vector<int> a) {
    std::vector<int> temp(a.size());
    i64 inversions = 0;    
    auto merge = [&](int left, int mid, int right, auto& self) {
        int i = left, j = mid + 1, k = left;
        i64 inv = 0;
        
        while (i <= mid && j <= right) {
            if (a[i] <= a[j]) {
                temp[k++] = a[i++];
            } else {
                temp[k++] = a[j++];
                inv += mid - i + 1;
            }
        }
        while (i <= mid) {
            temp[k++] = a[i++];
        }
        while (j <= right) {
            temp[k++] = a[j++];
        }        
        for (int p = left; p <= right; p++) {
            a[p] = temp[p];
        }
        return inv;
    };    
    auto mergeSort = [&](int left, int right, auto& self) -> i64 {
        if (left >= right) return 0;
        int mid = left + (right - left) / 2;
        i64 inv = 0;
        inv += self(left, mid, self);
        inv += self(mid + 1, right, self);
        inv += merge(left, mid, right, self);
        return inv;
    };
    if (a.empty()) return 0;
    return mergeSort(0, a.size() - 1, mergeSort);
}
void solve() {
    int n;
    cin >> n;
    std::vector<int>a(n);
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }
    std::vector<int> even, odd;
    for (int i = 0; i < n; i++) {
        if (i & 1) {
            odd.push_back(i);
        } else {
            even.push_back(i);
        }
    }
    std::sort(odd.begin(), odd.end(), [&](int i, int j) -> bool {
        return a[i] < a[j];
    });
    std::sort(even.begin(), even.end(), [&](int i, int j) -> bool {
        return a[i] < a[j];
    });
    std::vector<int> ans(n);
    int oi = 0, ei = 0;
    for (int i = 0; i < n; i++) {
        if (i & 1) {
            ans[i] = a[odd[oi++]];
        } else {
            ans[i] = a[even[ei++]];
        }
    }
    if ((countInversions(odd) - countInversions(even)) & 1) {
        std::swap(ans[n - 1], ans[n - 3]);
    }
    for (int i = 0; i < n; i++) {
        cout << ans[i] << " \n"[i == n - 1];
    }
}

E

1. 两个以上相同的数字，对于中间的数字来说没有意义，那就只考虑两个相同的数字
2. 要把相同的数字尽量向两侧放
3. 如果 $x$ 数字配对了，并且还有比 $x$ 更小的数字未使用，那么 $x$ 可以改为未使用的比 $x$ 更小的数字

然后总结规则，发现更小的数字有更多的选择位置，因此最终所有匹配的数字一定是 $1,2,3,4,…$，那么最终的答案就是 $$(max(idx_1)-min(idx_1))+(max(idx_2)-min(idx_2)+(max(idx_3)-min(idx_3)))+…=(max(idx_1)+max(idx_2)+max(idx_3)-(min(idx_1)+min(idx_2)+min(idx_3)+…)$$，所以考虑 $pre[i]$ 为可以匹配 1~i 的数字，最少的需要的 1~pre[i] 的数组元素，$suf[i]$ 同理。这样，答案就是满足 $pre[i]< suf[i]$ 的 $ans=\sum_i(suf[i]-pre[i])$。

接下来考虑如何求 pre 和 suf。从前往后遍历a数组，应该让当前元素 $x$ 变为尽可能大的数字，因为之后如果有更小的数字，它不会去抢占位置；如果没有，它自身也可以变为更小的数字。

可以使用一个 std::set 来记录当前未匹配过的元素，对当前元素 $x$ 匹配 set 中 $\le x$ 的最大的元素，匹配过后再从中删去。

void solve() {
    int n;
    cin >> n;
    std::vector<int> a(n);
    for (int &x : a) {
        cin >> x;
    }
    std::vector<int> pre(n), suf(n);
    auto s = std::views::iota(1, n + 1) | std::ranges::to<std::set<int>>();
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        auto p = s.upper_bound(a[i]);
        if (p != s.begin()) {
            pre[cnt++] = i;
            s.erase(--p);            
        }
    }
    s = std::views::iota(1, n + 1) | std::ranges::to<std::set<int>>();
    cnt = 0;
    for (int i = n - 1; i >= 0; i--) {
        auto p = s.upper_bound(a[i]);
        if (p != s.begin()) {
            suf[cnt++] = i;
        }
        s.erase(--p);
    }
    i64 ans = 0;
    for (int i = 0; i < n; i++) {
        if (pre[i] < suf[i]) {
            ans += suf[i] - pre[i];
        } else break;
    }
    cout << ans << "\n";
}

f

对一个 $cute$ 的子数组（排列），它的 LIS 和 LDS 一定包含且仅包含一个公共的元素：
证明：

设 LIS 为 $a_1,a_2,a_3,…,a_n$ LDS 为 $b_1, b_2,b_3,…,b_m$

1. 存在性：可知一定满足 $b_1>a_1$，$a_n>b_m$，则{a}，{b}一定包含相同元素。
2. 唯一性：如果有两个或两个元素以上同时属于{a}和{b}，则不满足递增或者递减。

所以一个子数组是 cute 的，当且仅当它其中的所有元素都是 LIS 或 LDS 中的元素。

按公共元素为 $p[i]$ 枚举，那么满足条件子数组最左端点内要满足大于 $p[i]$ 的元素递减，小于 $p[i]$ 的元素递增，设 $l[i]$ 为当前位置合法的最左端点，满足 $l[i]\sim i$ 内的所有下标都可以作为左端点，同理 $r[i]$。

每次寻找介于 $p[i-1]$ 和 $p[i]$ 之间的数字出现的最右下标 $f[i]$，取 $l[i] = min(l[i-1],f[i])$。右端点同理。

用线段树维护出现的元素的下标。

template <typename Info>
struct Segment_Tree {
    using T = typename Info::_vt;
    
    int n;
    std::vector<Info> info;
    template <typename _Tp>
    inline int __lg(_Tp __n) {
        constexpr int _BIT_WIDTH = sizeof(_Tp) * __CHAR_BIT__;
        return _BIT_WIDTH - 1 - __builtin_clz(__n);
    }
    Segment_Tree() : n(0) {}
    Segment_Tree(int n_, Info v_ = Info()) {
        init(n_, v_);
    }
    template <typename U>
    Segment_Tree(std::vector<U> init_) {
        init(init_);
    }
    void init(int n_, Info v_ = Info()) {
        init(std::vector(n_, v_));
    }
    template <typename U>
    void init(std::vector<U> init_) {
        n = init_.size();
        info.assign(4 << __lg(n), Info());
        std::function<void(int, int, int)> build = [&](int p, int l, int r) {
            if (r - l == 1) {
                info[p] = init_[l];
                return;
            }
            int m = (l + r) >> 1;
            build(p << 1, l, m);
            build(p << 1 | 1, m, r);
            pull(p);
        };
        build(1, 0, n);
    }
    void pull(int p) {
        info[p] = info[p << 1] + info[p << 1 | 1];
    }
    void modify(int p, int l, int r, int x, const Info &v) {
        if (l > x || r <= x) return;
        else if (r - l == 1) {
            info[p] = v;
        } else {
            int m = (l + r) >> 1;
            modify(p << 1, l, m, x, v);
            modify(p << 1 | 1, m, r, x, v);
            pull(p);
        }
    }
    void modify(int x, const Info &v) {
        modify(1, 0, n, x, v);
    }
    Info rangeQuery(int p, int l, int r, int x, int y) {
        if (l >= y || r <= x) return Info();
        if (l >= x && r <= y) return info[p];
        int m = (l + r) >> 1;
        return rangeQuery(p << 1, l, m, x, y) + rangeQuery(p << 1 | 1, m, r, x, y);
    }
    Info rangeQuery(int l, int r) {
        return rangeQuery(1, 0, n, l, r);
    }
    template <typename F>
    int findFirst(int p, int l, int r, int x, int y, F &&pred) {
        if (l >= y || r <= x) return -1;
        if (l >= x && r <= y && !pred(info[p])) return -1;
        if (r - l == 1) return l;
        int m = (l + r) >> 1;
        int res = findFirst(p << 1, l, m, x, y, pred);
        if (res == -1) {
            res = findFirst(p << 1 | 1, m, r, x, y, pred);
        }
        return res;
    }
    template <typename F>
    int findFirst(int l, int r, F &&pred) {
        return findFirst(1, 0, n, l, r, pred);
    }
    template <typename F>
    int findLast(int p, int l, int r, int x, int y, F &&pred) {
        if (l >= y || r <= x) return -1;
        if (l >= x && r <= y && !pred(info[p])) return -1;
        if (r - l == 1) return l;
        int m = (l + r) >> 1;
        int res = findLast(p << 1 | 1, m, r, x, y, pred);
        if (res == -1) {
            res = findLast(p << 1, l, m, x, y, pred);
        }
        return res;
    }
    template <typename F>
    int findLast(int l, int r, F &&pred) {
        return findLast(1, 0, n, l, r, pred);
    }
};

template<typename T>
struct Info1 {
    using _vt = T;
    
    T g = -1;
    Info1(T g = -1) : g(g) {}
    Info1 operator+(const Info1 &other) const {
        return {std::max(g, other.g)};
    }
};
int n;
template<typename T>
struct Info2 {
    using _vt = T;
    
    T g = n;
    Info2(T g = n) : g(g) {}
    Info2 operator+(const Info2 &other) const {
        return {std::min(g, other.g)};
    }
};
void solve() {
    cin >> n;
    std::vector<int> a(n);
    for (int &x : a) {
        cin >> x;
        x--;
    }
    std::vector<int> l(n, -1), r(n, n);
    Segment_Tree<Info1<int>> seg1(std::vector<int>(n, -1));
    seg1.modify(a[0], Info1<int>(0));
    Segment_Tree<Info2<int>> seg2(std::vector<int>(n, n));
    seg2.modify(a[n - 1], Info2<int>(n - 1));
    for (int i = 1; i < n; i++) {
        l[i] = std::max(l[i - 1], seg1.rangeQuery(std::min(a[i - 1], a[i]) + 1, std::max(a[i - 1], a[i])).g);
        seg1.modify(a[i], Info1<int>(i));
    }
    for (int i = n - 2; i >= 0; i--) {
        int t = seg2.rangeQuery(std::min(a[i], a[i + 1]) + 1, std::max(a[i], a[i + 1])).g;
        r[i] = std::min(r[i + 1], t);
        seg2.modify(a[i], Info2<int>(i));
    }
    i64 ans = r[0];
    for (int i = 1; i < n; i++) {
        ans += r[i - 1] - i;
        ans += (i - l[i]) * (r[i] - r[i - 1]);
    }
    cout << ans << "\n";
}