题解 CF986B 【Petr and Permutations】

Mr_Wu · 2018-07-24 20:18:14 · 题解

首先，我们需要一个引理：交换序列的任意两元素，序列的逆序数的奇偶性必定发生改变。

如何证明？

反正我不会证我是手推瞎猜的

显然3n与7n+1的奇偶性不同。

那么Petr和Alex交换后的序列逆序数奇偶性也不同。

算出给定序列逆序数，判断奇偶性即可。

这里n<=10^6，普通的O(n^2)算法肯定不行啊。

树状数组O(n\log{n})。

我们记x[i]为a[1],a[2],...,a[n-1]中比a[i]大的数的个数，例如序列

记x[1]=0, x[2]=0, x[3]=1, x[4]=0, x[5]=2

那么逆序数个数就是x[1]+x[2]+...+x[n]，在这里就是3。（这里的逆序数是指数对(i,j)满足i<j且a[i]>a[j]的）

开一个桶，从1到n循环，每次记x[i]=sum(a[i],n)，然后bucket[i]=1.

我们来模拟这个过程，以上文提到的序列为例。

最后累加，得出逆序数。

可这跟树状数组有什么关系？

每次求和就是区间求和，bucket[i]=1就是单点修改。

至于树状数组是什么...qwq

参考代码：

#include <cstdio>

const int MAXN = 1000005;
int tree[MAXN], n, a[MAXN], ans = 0;

int lowbit(int x)
{
    return x & -x;
} //lowbit qwq

void insert(int pos, int k)
{
    if (pos < 1) return;
    while (pos <= n)
    {
        tree[pos] += k;
        pos += lowbit(pos);
    }
} //单点修改

int query(int pos)
{
    int ret = 0;
    while (pos)
    {
        ret += tree[pos];
        pos -= lowbit(pos);
    }
    return ret;
} //(1-pos)的查询，查询[l,r]的和用query(r)-query(l-1)

int main()
{
    scanf("%d", &n);
    int i;
    for (i = 1; i <= n; i++) scanf("%d", &a[i]);
    for (i = 1; i <= n; i++)
    {
        ans = (ans + query(n) - query(a[i] - 1)) % 2; 
        //直接记录答案的奇偶性了，query(n)-query(a[i]-1)是sum(a[i],n)
        insert(a[i], 1);
        //单点修改
    }
    ans %= 2;
    if ((ans - 3 * n) % 2 == 0) printf("Petr"); //奇偶性判断
    else printf("Um_nik");
    return 0;
}