ARC043C 転倒距離

定义两个排列 $A, B$ 的距离为满足 $(i, j)$ 在 $A, B$ 中顺序相反的无序对数。现在给定排列 $A$ 和 $B$，构造一个排列 $C$ 使得 $dis(A, C) = dis(B, C)$。

若 $(i, j)$ 在 $A,B$ 中的相对位置相同，则对 $dis(A, C)$ 和 $dis(B, C)$ 有相同的贡献。若不同，则对其中一个有 $1$ 的贡献。容易发现有解当且仅当 $dis(A, B)$ 为偶数。将 $A$ 映射为 $1, 2\dots n$。则 $dis(A, B)$ 等于 $B$ 的逆序对数，设为 $s$。

现在我们要构造一个 $C$ 使得 $B$ 中一半的逆序对变成正序对。设 $p$ 为最早满足 $[1, p]$ 中逆序对数大于 $\frac s2$ 的位置。将 $1$ 到 $p – 1$ 排序，再将 $p$ 插入到中间即可。

看代码应该好懂一些吧。

#include <bits/stdc++.h>

const int N = 1e5 + 10;


template<typename T = int> inline T read()
{
    T x = 0, f = 0; char ch = getchar();
    while (!isdigit(ch)) f |= ch == '-', ch = getchar();
    while ( isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();
    return f ? -x : x;
}

struct BIT
{
    int f[N];
    #define lowbit(x) (x & -x)

    inline void Add(int x, int dat = 1)
    {
        for (; x < N; x += lowbit(x)) f[x] += dat;
    }

    inline int Ask(int x)
    {
        int res = 0;
        for (; x; x -= lowbit(x)) res += f[x];
        return res;
    }
}T;

int a[N], A[N], b[N], s[N];

int main()
{
    int n = read(), p = 0; int64_t sum = 0;
    for (int i = 1; i <= n; ++i) a[A[i] = read()] = i;
    for (int i = 1; i <= n; ++i) b[i] = a[read()];
    for (int i = 1; i <= n; ++i) s[i] = T.Ask(N - 1) - T.Ask(b[i]), T.Add(b[i]);
    for (int i = 1; i <= n; ++i) sum += s[i];
    if (sum & 1) return puts("-1"), 0; sum >>= 1;
    for (int i = 1; i <= n; ++i)
    {
        if (sum < s[i]) {p = i; break;}
        sum -= s[i];
    }
    std::sort(b + 1, b + p);
    for (int i = 1; i <= sum; ++i) std::swap(b[p], b[p - 1]), --p;
    for (int i = 1; i <= n; ++i) printf("%d ", A[b[i]]); puts("");
    return 0;
}

$2020.12.17$ 准备退役了。终究还是会退役啊。

我也不知道为啥当初要选择来海亮学信奥，可能只是为了逃避文化课，来打游戏，颓废。但是，我迟早要面对它。现在文化课给我的压力是很大的，我发现老师上课讲的我基本上就完全不会，小机房也没啥学文化课的氛围。而且信奥方面，我现在模拟赛天天爆 $0$ 垫底。我越发感觉自己不适合学信奥。我感觉我现在再这么搞下去很不行，于是我准备退役。

回顾这一整年的学习经历，有一说一，我还是学到了一些东西的。但是从大体来说，我颓废的时间太多。平常的题目一般就抄个题解，有时候连抄都不抄，就直接复制粘贴上去。模拟赛也基本上不认真打，要么就是网上找原题，或者拿同学的代码。实在搞不动就直接写个最低档暴力颓废。现在一认真打，问题马上就暴露出来。这样一整年搞下来，我现在进省队的希望非常小，我自己认为，我已经无法达到更高的水平了。

我总结出了我退役的四点原因：

• 自身实力不足。$ZJOI2020$ 垫底，$APIO2020$ 近乎爆 $0$，$NOI$ 同步赛完全爆 $0$，这都显示出我的实力不足。确实应该退役。
• 文化课不足以支持我停课学信奥，小机房没有学习氛围。因为我在机房就会划水打游戏，影响了小机房学习氛围。而且我到寝室学习就会影响同学（其实是同学说我内卷），导致我也不能在寝室学习。这样我就没有学习文化课的时间了。这也说明我确实应该退役
• 自身信心不足。通过这几次考试，我每次垫底，而且得分都是最高分的一半不到。尤其是某一次考试，我的得分是最高分的 $\frac 1{10}$。这也极大的打击了我的信心。
• 来自其他各方面的压力。其实我感觉我的家长，老师其实也不是很支持我继续学下去，我也难以承受他们给我带来的压力。而且通过他们对我的批评教育，我也认识到我自己还有很多不足，也说明了我确实是一个失败者。

最近，我看了时队的一篇文章，这篇文章说了关于沉没成本的问题，我也意识到我确实不能继续再这样走下去，不能总是以自己以前花了多少时间来找借口，要赶紧退役。

谢谢朋友们。

upd1 on 2020.12.18

以后就突然想到什么就更新一下吧。

我认为，退役要乘早，但是要经过慎重考虑。如果你在学习过程中一直想着退役，那么你的学习就不会成功（想法决定做法）。退役要抓紧时间，不要犹豫，这样你的学习效率就会下降（就和我一样一事无成）。

upd2 on 2020.12.24

昨天举办表彰大会，从大会上，我见识到了许多强者，也越发感觉自己的弱小。我也感觉到其实现在的形势也不适合我继续学下去（看起来维尼都不支持我学）。

Rt