题解 | # D. Yet Another Sorting Problem #

$[逆序数]$

在上上上篇题解中有两个重要结论：

任意一个排列一定可以唯一的分解成若干个互不相交的置换环并集
假设长度为 $n$ 的排列有 $c$ 个置换环，那么交换任意两个元素使得排列升序的最少操作次数为 $n-c$ 次

现在补充两个排列与逆序对的结论：

一个排列中，交换任意两个元素，逆序对数的奇偶性一定改变
排列的逆序对数与 $(n-c)$ 的奇偶性相同

证明第一个结论：

如果交换的位置相邻，那么逆序对数加 $1$ 或者减 $1$ ，那么奇偶性改变
如果交换的位置不相邻，设交换的两个位置之间有 $k$ 个元素，那么两个位置相当于与中间 $k$ 个元素都进行了一次交换，所以是 $2\times k$ 次交换，再加上两个位置的交换，所以是 $2\times k + 1$ 次交换，所以奇偶性改变

证明第二个结论：

将排列通过交换顺序使其升序：

如果可以交换任意两个位置，那么最小操作次数是 $n-c$ 次
如果只能是交换相邻两个位置，那么最小操作次数是排列的逆序对数次

可见最终的目的是使得排列升序，而升序的逆序对数是 $0$ ，所以排列的逆序对数与 $(n-c)$ 的奇偶性相同

题目一：D. Yet Another Sorting Problem，https://codeforces.com/contest/1591/problem/D

思考 $1，2，3$ 的 $6$ 种排列： $[1,2,3]$ ， $[1,3,2]$ ， $[2,1,3]$ ， $[2,3,1]$ ， $[3,1,2]$ ， $[3,2,1]$

其中 $[1,2,3]$ ， $[3,1,2]$ ， $[2,3,1]$ 这 $3$ 个排列可以通过操作相互到达，其逆序对数分别为 $0，2，2$

其中 $[1,3,2]$ ， $[2,1,3]$ ， $[3,2,1]$ 这 $3$ 个排列可以通过操作相互到达，其逆序对数分别为 $1，1，3$

可以分析出执行操作时，逆序对数的奇偶性没有发生变化，故直接判断 $a_{1},a_{2},...,a_{n}$ 的逆序对数奇偶性即可

$Wrong \ answer\ on \ test\ 2$

哦，不一定是排列，可能是 $1，1，2$ 这种，再和上面一样的分析，发现逆序对数可以为 $0,1,2$ ，可以消除奇偶性

那么如果 $a_{1},a_{2},...,a_{n}$ 的逆序对数为偶数，直接输出 $YES$ ，否则判断是否有两个相同的数，如果有输出 $YES$ ，否则输出 $NO$

总代码：

#include<bits/stdc++.h>
using namespace std;

#define endl '\n'
#define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define HelloWorld IOS;


const int N = 500010;

int a[N], b[N], sum;

void quick_sort(int l, int r){
    if(l >= r) return ;
    int mid = (l + r) / 2;
    quick_sort(l, mid);
    quick_sort(mid + 1, r);
    int i = l, j = mid + 1, k = l;
    while(i <= mid && j <= r){
        if(a[i] <= a[j]) b[k ++] = a[i ++];
        else{
            b[k ++] = a[j ++];
            sum += mid - i + 1;
        }
    }
    while(i <= mid) b[k ++] = a[i ++];
    while(j <= r) b[k ++] = a[j ++];
    for(int i = l; i <= r; i ++) a[i] = b[i];
}

void solve(){
    int n; cin >> n;
    for(int i = 1; i <= n; i ++) cin >> a[i];
    sum = 0;
    quick_sort(1, n);
    if(sum & 1){
        for(int i = 1; i <= n - 1; i ++){
            if(a[i] == a[i + 1]){
                cout << "YES" << endl;
                return ;
            }
        }
        cout << "NO" << endl;
    }
    else cout << "YES" << endl; 
    return ;
}

signed main(){
    HelloWorld;
    
    int tt = 1; 
    cin >> tt;
    while(tt --) solve();
    return 0;
}

题目二： D. Inversion Counting，https://codeforces.com/contest/911/problem/D

区间 $[l,r]$ 翻转时，逆序对数的变化是 $\frac{(r-l+1)\times (r -l)}{2}$ ，所以累加初始状态的逆序对数，判断奇偶性即可

总代码：

#include<bits/stdc++.h>
using namespace std;

#define endl '\n'
#define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define HelloWorld IOS;


const int N = 2000;

int n, m, a[N], b[N];
int sum;

void quick_sort(int l, int r){
    if(l >= r) return;
    int mid = (l + r) / 2;
    quick_sort(l, mid);
    quick_sort(mid + 1, r);
    int i = l, j = mid + 1, k = l;
    while(i <= mid && j <= r){
        if(a[i] <= a[j]) b[k ++] = a[i ++];
        else{
            b[k ++] = a[j ++];
            sum += mid - i + 1;
        }
    }
    while(i <= mid) b[k ++] = a[i ++];
    while(j <= r) b[k ++] = a[j ++];
    for(int i = l; i <= r; i ++) a[i] = b[i];
}


void solve(){
    
    cin >> n;
    for(int i = 1; i <= n; i ++) cin >> a[i];
    sum = 0;
    quick_sort(1, n);
    cin >> m;
    while(m --){
        int l, r; cin >> l >> r;
        sum += (r - l + 1) * (r - l) / 2;
        if(sum & 1) cout << "odd" << endl;
        else cout << "even" << endl;
    }
    return ;
}

signed main(){
    HelloWorld;
    
    int tt = 1; 
    while(tt --) solve();
    return 0;
}

题目三：E. Petr and Permutations，https://codeforces.com/contest/987/problem/E

交换任意两个元素，排列的逆序对数奇偶性发生变化，

当 $n$ 为奇数时， $3n$ 为奇数， $7n+1$ 为偶数
当 $n$ 为偶数时， $3n$ 为偶数， $7n+1$ 为奇数

所以一开始从 $1$ 到 $n$ 的自然序列排列进行 $3n$ 或 $7n+1$ 次交换操作后，逆序对数的奇偶性与 $n$ 的奇偶性以及操作的次数的奇偶性有关，现在已知 $n$ 的奇偶性，也可以求出操作后排列的逆序对数的奇偶性，所以反推操作次数的奇偶性即可

总代码：

#include<bits/stdc++.h>
using namespace std;

#define endl '\n'
#define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define HelloWorld IOS;


const int N = 1000100;

int n, a[N], b[N];
int sum;

void quick_sort(int l, int r){
    if(l >= r) return;
    int mid = (l + r) / 2;
    quick_sort(l, mid);
    quick_sort(mid + 1, r);
    int i = l, j = mid + 1, k = l;
    while(i <= mid && j <= r){
        if(a[i] <= a[j]) b[k ++] = a[i ++];
        else{
            b[k ++] = a[j ++];
            sum += mid - i + 1;
        }
    }
    while(i <= mid) b[k ++] = a[i ++];
    while(j <= r) b[k ++] = a[j ++];
    for(int i = l; i <= r; i ++) a[i] = b[i]; 
}

void solve(){

    cin >> n;
    for(int i = 1; i <= n; i ++) cin >> a[i];
    sum = 0;
    quick_sort(1, n);
    if(n & 1){
        if(sum & 1) cout << "Petr" << endl;
        else cout << "Um_nik" << endl;
    }
    else{
        if(sum & 1) cout << "Um_nik" << endl;
        else cout << "Petr" << endl;
    }
    return ;
}

signed main(){
    HelloWorld;
    
    int tt = 1; 
    while(tt --) solve();
    return 0;
}

题目四：F - Simultaneous Swap，https://atcoder.jp/contests/abc296/tasks/abc296_f

和题目一有些类似，不多写了

总代码：

#include<bits/stdc++.h>
using namespace std;

#define endl '\n'
#define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define HelloWorld IOS;



const int N = 200010;
int n, a[N], b[N], a1[N], b1[N];
int sum1, sum2;

void quick_sort_a(int l, int r){
    if(l >= r) return ;
    int mid = (l + r) / 2;
    quick_sort_a(l, mid);
    quick_sort_a(mid + 1, r);
    int i = l, j = mid + 1, k = l;
    while(i <= mid && j <= r){
        if(a[i] <= a[j]) a1[k ++] = a[i ++];
        else{
            a1[k ++] = a[j ++];
            sum1 += mid - i + 1;
        }
    }
    while(i <= mid) a1[k ++] = a[i ++];
    while(j <= r) a1[k ++] = a[j ++];
    for(int i = l; i <= r; i ++) a[i] = a1[i];
}

void quick_sort_b(int l, int r){
    if(l >= r) return ;
    int mid = (l + r) / 2;
    quick_sort_b(l, mid);
    quick_sort_b(mid + 1, r);
    int i = l, j = mid + 1, k = l;
    while(i <= mid && j <= r){
        if(b[i] <= b[j]) b1[k ++] = b[i ++];
        else{
            b1[k ++] = b[j ++];
            sum1 += mid - i + 1;
        }
    }
    while(i <= mid) b1[k ++] = b[i ++];
    while(j <= r) b1[k ++] = b[j ++];
    for(int i = l; i <= r; i ++) b[i] = b1[i];
}

void solve(){
    
    cin >> n;
    for(int i = 1; i <= n; i ++) cin >> a[i];
    for(int i = 1; i <= n; i ++) cin >> b[i];
    sum1 = sum2 = 0;
    quick_sort_a(1, n);
    quick_sort_b(1, n);
    for(int i = 1; i <= n; i ++){
        if(a[i] != b[i]){
            cout << "No" << endl;
            return ;
        }
    }
    if((sum1 & 1) == (sum2 & 1)) cout << "Yes" << endl;
    else{
        for(int i = 1; i <= n - 1; i ++){
            if(a[i] == a[i + 1]){
                cout << "Yes" << endl;
                return ;
            }
        }
        cout << "No" << endl;
    }
    return ;
}

signed main(){
    HelloWorld;
    
    int tt = 1; 
    while(tt --) solve();
    return 0;
}