题目描述

Description

马达加斯加贞鱼是一种神奇的双脚贞鱼，它们把自己的智慧写在脚上——每只贞鱼的左脚和右脚上各有一个数。有
一天，K只贞鱼兴致来潮，排成一列，从左到右第i只贞鱼会在右脚写Ai，左脚上写上i；第二年，这K只贞鱼以右脚
的数为第一关键字、左脚的数为第二关键字，从小到大排成一列。然后，它们决定重编号，从左到右第i只贞鱼会
在右脚上写上左脚的数，在左脚上写i；第三年，它们按第二年的方法重排列、重编号......N年后，对于从左到右
第i和第j贞鱼，若i < j且第i只贞鱼右脚上的数比第j只贞鱼右脚上的数大，则称它们为一对“超级贞鱼”。问一共
有多少对“超级贞鱼”？

Input

共3行，第一行一个正整数K，表示有K只贞鱼。
第二行K个正整数，第i个数表示Ai。
第三行一个非负整数N，表示年数。
K≤2×10^6， Ai≤10^9，N≤10^18

Output

一个整数，表示“超级贞鱼”的对数。

Sample Input

6
5 2 6 3 1 7
0

Sample Output

7

题目分析

显而易见 第二次排序会排回原数列 那我们可以对年数%2 分类讨论就可以了 么?????
不可以！ 这题卡常
再仔细观察样例 发现:不论怎么排 能产生逆序对的数的相对位置是不变的
那不就是归并排序求逆序对裸题了= =

#include <cstdio>
#include <cstring>
#include <set>
#include <map>
#include <vector>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
int n;
int val[3001000],tmp[3001000];
long long ans;
void merge(int l,int mid,int r)
{
    int i=l,j=mid+1,k=l;
    while(i<=mid&&j<=r)
    {
        if(val[i]>val[j])
            tmp[k++]=val[j++],ans+=mid-i+1;
        else tmp[k++]=val[i++];
    }
    while(i<=mid) tmp[k++]=val[i++];
    while(j<=r) tmp[k++]=val[j++];
    for(i=l;i<=r;i++) val[i]=tmp[i];
}
void sor(int l,int r)
{
    if(l==r) return ;
    int mid=(l+r)>>1;
    sor(l,mid),sor(mid+1,r);
    merge(l,mid,r);
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&val[i]);
    sor(1,n);
    printf("%lld",ans);
    return 0;
}