P10068 [CCO 2023] Line Town

EuphoricStar · 2025-11-21 22:20:48 · 题解

这题的特殊性质很有引导性，会了全部特殊性质基本就会正解了。

首先考虑 |a_i| 互不相同怎么做。

发现一个数最后的符号只和它移动距离的奇偶性和原来的符号有关，并且最终序列的绝对值是先递减后递增。

那么自然考虑，按绝对值从大到小，在序列两端填数。设 f_{i, 0/1} 表示考虑了绝对值 \ge i 的数，序列左端填了偶数个 / 奇数个数，的最小交换次数。交换次数就是它在原序列中左边或右边（左边还是右边取决于它被填到最左边还是最右边）比它小的数的个数。时间复杂度 O(n \log n)，获得 \frac{7}{25} 的高分。

再考虑 |a_i| \le 1 怎么做。容易想到枚举最终有 i 个 0 换到最左边，但是这样仍然不好直接写出操作次数，因为交换就会变号比较麻烦。

那么有一个处理翻转相邻两位奇偶性的、比较经典的 trick 是翻转奇数位，到这题就是翻转奇数位的符号。这样的好处是操作变成直接交换相邻两个数，不用变号。

现在最终的状态形如 1, -1, \cdots 1, -1, 0, \cdots, 0, -1, 1, \cdots, -1, 1，其中最后一位是 1 还是 -1 取决于 n 的奇偶性。那么我们枚举了 i 之后，序列中每一个 1 和 -1 的最终相对位置（在所有 \pm 1 中是从左往右第几个）都能算出来。

那么算交换次数就是 \pm 1 和 0 的交换次数，加上 \pm 1 内部的交换次数。\pm 1 和 0 的交换次数等于一个 \pm 1 左边或右边（左边还是右边取决于它被填到最左边还是最右边）0 的个数，\pm 1 内部的交换次数就是每个 \pm 1 原来的相对位置减去最终的相对位置绝对值之和。

不难通过一些预处理做到 O(n)。拼上 |a_i| 互不相同的做法，获得 \frac{20}{25} 的高分。

那么做到这一步其实可以发现正解就是上面两个做法拼起来。仍然是按 |a_i| 从大到小 DP，设当前考虑的绝对值是 k，把 k 看成 1，-k 看成 -1，绝对值 < k 的数看成 0，然后套用 |a_i| \le 1 的做法即可。

实现时要特别小心奇偶性的处理。

最终总时间复杂度 O(n \log n)，但是除了离散化和计算每个数左边（和右边）比它小的数的个数时间复杂度是 O(n \log n) 之外，其他的部分都是 O(n) 的。

:::info[代码]

// Problem: P10068 [CCO 2023] Line Town
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P10068
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))

using namespace std;
using ll = long long;
using ull = unsigned long long;
using db = double;
using ldb = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

namespace IO {
    const int maxn = 1 << 20;

    char ibuf[maxn], *iS, *iT, obuf[maxn], *oS = obuf;

    inline char gc() {
        return (iS == iT ? iT = (iS = ibuf) + fread(ibuf, 1, maxn, stdin), (iS == iT ? EOF : *iS++) : *iS++);
    }

    template<typename T = int>
    inline T read() {
        char c = gc();
        T x = 0;
        bool f = 0;
        while (c < '0' || c > '9') {
            f |= (c == '-');
            c = gc();
        }
        while (c >= '0' && c <= '9') {
            x = (x << 1) + (x << 3) + (c ^ 48);
            c = gc();
        }
        return f ? ~(x - 1) : x;
    }

    inline int reads(char *s) {
        char c = gc();
        int len = 0;
        while (isspace(c)) {
            c = gc();
        }
        while (!isspace(c) && c != -1) {
            s[len++] = c;
            c = gc();
        }
        s[len] = '\0';
        return len;
    }

    inline string reads() {
        char c = gc();
        string s;
        while (isspace(c)) {
            c = gc();
        }
        while (!isspace(c) && c != -1) {
            s += c;
            c = gc();
        }
        return s;
    }

    inline void flush() {
        fwrite(obuf, 1, oS - obuf, stdout);
        oS = obuf;
    }

    struct Flusher {
        ~Flusher() {
            flush();
        }
    } AutoFlush;

    inline void pc(char ch) {
        if (oS == obuf + maxn) {
            flush();
        }
        *oS++ = ch;
    }

    inline void write(char *s) {
        for (int i = 0; s[i]; ++i) {
            pc(s[i]);
        }
    }

    inline void write(const char *s) {
        for (int i = 0; s[i]; ++i) {
            pc(s[i]);
        }
    }

    template<typename T>
    inline void write(T x) {
        static char stk[64], *tp = stk;
        if (x < 0) {
            x = ~(x - 1);
            pc('-');
        }
        do {
            *tp++ = x % 10;
            x /= 10;
        } while (x);
        while (tp != stk) {
            pc((*--tp) | 48);
        }
    }

    template<typename T>
    inline void writesp(T x) {
        write(x);
        pc(' ');
    }

    template<typename T>
    inline void writeln(T x) {
        write(x);
        pc('\n');
    }
}

using IO::read;
using IO::reads;
using IO::write;
using IO::pc;
using IO::writesp;
using IO::writeln;

const int maxn = 500100;
const ll inf = 0x3f3f3f3f3f3f3f3fLL;

int n, a[maxn], lsh[maxn], tot, ls[maxn], rs[maxn], b[maxn], c[maxn], d[maxn];
ll f1[maxn], f2[maxn], f3[maxn], f4[maxn], pre[2][maxn], suf[2][maxn];
bool vis[maxn];
vector<int> ap[maxn];

namespace BIT {
    int c[maxn];

    inline void update(int x, int d) {
        for (int i = x; i <= tot; i += (i & (-i))) {
            c[i] += d;
        }
    }

    inline int query(int x) {
        int res = 0;
        for (int i = x; i; i -= (i & (-i))) {
            res += c[i];
        }
        return res;
    }
}

void solve() {
    n = read();
    for (int i = 1; i <= n; ++i) {
        a[i] = read();
        if (a[i] < 0) {
            a[i] = -a[i];
            vis[i] = 1;
        }
        lsh[++tot] = a[i];
    }
    sort(lsh + 1, lsh + tot + 1);
    tot = unique(lsh + 1, lsh + tot + 1) - lsh - 1;
    for (int i = 1; i <= n; ++i) {
        a[i] = lower_bound(lsh + 1, lsh + tot + 1, a[i]) - lsh;
        ++b[a[i]];
    }
    for (int i = 1; i <= tot; ++i) {
        b[i] += b[i - 1];
    }
    for (int i = 1; i <= n; ++i) {
        ls[i] = BIT::query(a[i] - 1);
        rs[i] = b[a[i] - 1] - ls[i];
        BIT::update(a[i], 1);
    }
    mems(b, 0);
    for (int i = 1; i <= n; ++i) {
        if (vis[i] ^ (i & 1)) {
            a[i] = -a[i];
        }
        ap[abs(a[i])].pb(i);
    }
    ll f[2] = {0, inf};
    int r = n;
    for (int k = tot; k; --k) {
        if (lsh[k] == 0) {
            break;
        }
        ll g[2] = {inf, inf};
        int m1 = 0, m2 = 0, cnt = 0;
        for (int i : ap[k]) {
            ++cnt;
            if (a[i] > 0) {
                b[++m1] = i;
                d[i] = cnt;
            } else {
                c[++m2] = i;
                d[i] = cnt;
            }
        }
        for (int i = 1; i <= m1; ++i) {
            f1[i] = f1[i - 1] + ls[b[i]];
            f2[i] = f2[i - 1] + rs[b[i]];
            b[i] = d[b[i]];
        }
        for (int i = 1; i <= m2; ++i) {
            f3[i] = f3[i - 1] + ls[c[i]];
            f4[i] = f4[i - 1] + rs[c[i]];
            c[i] = d[c[i]];
        }
        for (int j = 0; j <= 1; ++j) {
            for (int i = 1, p1 = 1, p2 = 1; i <= m1 + m2; ++i) {
                pre[j][i] = pre[j][i - 1];
                if ((j ^ i) & 1) {
                    pre[j][i] += abs(b[p1++] - i);
                } else {
                    pre[j][i] += abs(c[p2++] - i);
                }
            }
        }
        suf[0][m1 + m2 + 1] = suf[1][m1 + m2 + 1] = 0;
        for (int j = 0; j <= 1; ++j) {
            for (int i = m1 + m2, o = (r & 1) ^ j, p1 = m1, p2 = m2; i; --i, o ^= 1) {
                suf[j][i] = suf[j][i + 1];
                if (o) {
                    suf[j][i] += abs(c[p2--] - i);
                } else {
                    suf[j][i] += abs(b[p1--] - i);
                }
            }
        }
        for (int j = 0; j <= 1; ++j) {
            for (int i = 0; i <= m1 + m2; ++i) {
                int x = (i + 1) >> 1, y = (i >> 1);
                if (j) {
                    swap(x, y);
                }
                int rx = m1 - x, ry = m2 - y;
                if (rx < 0 || ry < 0) {
                    continue;
                }
                if ((r ^ j) & 1) {
                    if (rx != ry && rx + 1 != ry) {
                        continue;
                    }
                } else {
                    if (rx != ry && rx != ry + 1) {
                        continue;
                    }
                }
                g[(i & 1) ^ j] = min(g[(i & 1) ^ j], f[j] + ((((f1[x] + f3[y] + f2[m1] - f2[x] + f4[m2] - f4[y]) << 1) + pre[j][i] + suf[j][i + 1]) >> 1));
            }
        }
        f[0] = g[0];
        f[1] = g[1];
        r -= (int)ap[k].size();
    }
    writeln(min(f[0], f[1]) > 1e18 ? -1 : min(f[0], f[1]));
}

int main() {
    int T = 1;
    // scanf("%d", &T);
    while (T--) {
        solve();
    }
    return 0;
}

:::