Lenstar的博客

博客

ARC043C 题解

2021-01-13 19:06:14 By Lenstar

ARC043C 転倒距離

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

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

现在我们要构造一个 C 使得 B 中一半的逆序对变成正序对。设 p 为最早满足 [1,p] 中逆序对数大于 s2 的位置。将 1p – 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;
}

评论

[+33]
谢谢!
  • 2021-02-13 07:29:34
  • Reply
Comment replies
Lenstar:感谢所有HY
Lenstar:感谢更多的HY
[+8]
lenstar ak ioi
  • 2021-10-13 19:23:22
  • Reply
[+7]
hello
  • 2021-02-15 06:28:43
  • Reply
Comment replies
admin:?你为什么不庆祝王鸿翼老板赚大钱
[+4]
我无敌了
  • 2021-02-16 09:22:45
  • Reply
[-3]
123
  • 2021-10-02 13:43:24
  • Reply

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。