CF986B Petr and Permutations 题解

· · 题解

Preface

安利博客与大号。

前置芝士。

Introduction

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

证明：

令 p_1<p_2。

当 p_2=p_1+1 时（交换相邻两个数），这一对数相对顺序改变，所以逆序对数加一或减一，逆序对奇偶性改变。

若不然，令 l=|p_1-p_2|-1，则先通过 l+1 次操作将 p_1 移动到 p_2 位置上，再用 l 次操作将 p_2 移动到 p_1 位置，共 2l+1 次操作。

命题获证。

又因为 3n 与 7n+1 奇偶性不同，两人交换后的序列逆序数奇偶性也不同。

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

逆序对可用树状数组维护，时间复杂度 O(n\log n)。

Code

#include<bits/stdc++.h> 
#define int long long
using namespace std;
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9') {
    x=x*10+ch-'0';
    ch=getchar();
}
    return x*f;
}
void write(int x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    if(x>9)
        write(x/10);
    putchar(x%10+'0');
    return;
}
int m,op,x,y;
long long last_val,now_val,k;
int a[1000001],rnk[1000001],tree[1000001],n;
int lowbit(int x){
    return (x)&(-x);
}
void update(int x,int d){
    while(x<=n){
        tree[x]+=d;
        x+=lowbit(x);
    } 
}
int query(int x){
    int sum=0;
    while(x){
        sum+=tree[x];
        x-=lowbit(x);
    }
    return sum;
}
long long ans;
bool cmp(int x,int y){
    if(a[x]==a[y]) return x>y;
    return a[x]>a[y];
}
signed main(){
    n=read();
    for(int i=1;i<=n;i++){
        a[i]=read();
    }
    for(int i=n;i>=1;i--){
        ans+=query(a[i]); 
        update(a[i],1);
    }
    ans%=2;
    n&=1;
    if(ans==n){
        printf("Petr");
    }
    else printf("Um_nik"); 
    return 0;
}