Codeforces Round 1040 (Div. 1 + 2)

Div2 C/Div1 A - Double Perspective

为了让 $f(S)-g(S)$ 最大化，我们总是贪心地选取线段：如果这条线段没有与之前选的线段构成环，那么就直接加入；否则，若构成了环，说明之前选择的线段可以恰好覆盖这条线段，这条线段的加入也不可能使得 $f(S)$ 更大，反而使 $g(S)$ 更大了。

判断线段是否构成环可以用并查集维护。时间复杂度 $O(n\cdot \alpha(n))$ 其中 $\alpha(n)$ 是并查集的复杂度。

AC Code

#include <bits/stdc++.h>
using pii = std::pair<int, int>;

template <class T>
using vec = std::vector<T>;

struct dsu {
    vec<int> fa, siz;
    dsu(int n = 0) { init(n); }
    void init(int n) {
        fa.resize(n + 1, 0);
        siz.resize(n + 1, 1);
        std::iota(fa.begin(), fa.end(), 0);
    }
    int root(int x) { return x == fa[x] ? x : fa[x] = root(fa[x]); }
    bool connected(int u, int v) { return root(u) == root(v); }
    bool merge(int u, int v) {
        int fu = root(u), fv = root(v);
        if (fu == fv) return false;
        if (siz[fu] > siz[fv]) std::swap(fu, fv);
        fa[fu] = fv;
        siz[fv] += siz[fu];
        return true;
    }
};

void run() {
    int n;
    std::cin >> n;
    vec<pii> a(n);
    for (auto &x : a) std::cin >> x.first >> x.second;

    dsu d(n * 2);
    vec<int> ans;
    for (int i = 0; i < n; i++) {
        if (d.connected(a[i].first, a[i].second)) continue;
        ans.push_back(i + 1);
        d.merge(a[i].first, a[i].second);
    }
    std::cout << ans.size() << "\n";
    for (auto i : ans) std::cout << i << " ";
    std::cout << "\n";
}

int main() {
#ifdef ONLINE_JUDGE
    std::cin.tie(0)->sync_with_stdio(0);
    std::cout.tie(0);
#endif
    int t;
    std::cin >> t;
    while (t--) run();
}

Div2 D/Div1 B - Stay or Mirror

考虑将 $a_i$ 换成 $2n-a_i$ . 对于 $j\lt i$ 的 $a_j$ 而言，若初始时 $a_j\lt a_i$ ，那么就算替换了也不会产生新的逆序对；对于 $j\gt i$ 若初始时 $a_j\lt a_i$ ，那么就算替换了， $(i,j)$ 仍然还是逆序对。

所以，对于 $a_i$ 只关心其前后 $\gt a_i$ 的元素数量，由于 $2n-a_i\ge n\ge a_i$ ，所以，一旦替换，则必然减少 $(x,i)$ 的逆序对数量，增加 $(i,y)$ 的逆序对数量。如果减少的比增加的多，那么就可以替换。

逆序对可以用树状数组统计，时间复杂度 $O(n\log n)$ .

AC Code

#include <bits/stdc++.h>

struct fenwick {
    std::vector<int> b;
    int n;

    fenwick(int n = 0) { init(n); }
    void init(int n) {
        this->n = n;
        b.assign(n + 1, 0);
    }
    void add(int p, int v) {
        for (; p <= n; p += p & -p) b[p] += v;
    }
    int sum(int p) {
        int s = 0;
        for (; p > 0; p -= p & -p) s += b[p];
        return s;
    }
    int sum(int l, int r) { return sum(r) - sum(l - 1); }
};

void run() {
    int n;
    std::cin >> n;
    std::vector<int> a(n);
    for (int i = 0; i < n; i++) std::cin >> a[i];

    fenwick F(n * 2), B(n * 2);
    for (int i = 0; i < n; i++) F.add(a[i], 1);
    for (int i = n - 1; i >= 0; i--) {
        F.add(a[i], -1);

        int f = F.sum(a[i] + 1, n * 2);
        int b = B.sum(a[i] + 1, n * 2 - a[i]);

        if (f >= b) a[i] = n * 2 - a[i];
        B.add(a[i], 1);
    }

    fenwick Q(n * 2);
    int ans = 0;
    for (int i = 0; i < n; i++) {
        ans += Q.sum(a[i] + 1, n * 2);
        Q.add(a[i], 1);
    }
    std::cout << ans << "\n";
}

int main() {
#ifdef ONLINE_JUDGE
    std::cin.tie(0)->sync_with_stdio(0);
    std::cout.tie(0);
#endif
    int t;
    std::cin >> t;
    while (t--) run();
}