UESTC - 1583 曜酱的心意 求逆序对

我觉得我不能不写这道题的题解。它帮了我很多。
题面看曜酱的心意
这个题题目背景简直是毒，我在吐槽曜酱全排列100000个数的同时不禁审视起这道题来。
把一个1-n的全排列通过不断交换相邻两个数字，改变成另一个1-n的全排列，求交换最小的次数。由于n<=100000，故要用nlogn算法。那很明显就是求逆序对了。
我们知道有两种算法，树状数组和归并排序。你在提交状态里看一下，40-50ms的基本是树状数组，60-70ms的是归并排序。我肯定是猜错了。都能过时限的情况下怎么样都无所谓了，而且令人惊讶的是所有题解都用的是树状数组，所以我用我说的归并排序法写。这里又不得不说一件事。一个月以前我看到这道题。那个时候我不会nlogn的写法，所以我去问大佬。大佬让我去看归并排序法求逆序对，然后我成功地猜到了初赛题。我十分地感谢这道题狗血的故事背景。
好了回到正题。那么是求哪个数组呢？首先读入第一个数组A的时候用数组K记录k[a[i]]=i;然后读入B之后将A转化为a[i]=k[b[i]],我也不知道为什么。然后就得到了这个数组，直接求它的逆序对就可以了。这里不得不吐槽一下数据，第一个点数据这么大，我还以为我什么地方错了，结果是没有开long long,我真的是吐血了。
还有一开始我想错了算法，以为是对A排序然后对对应的B数组求逆序对。看来我还是太年轻了。

#include<bits/stdc++.h>//Chika说希望和我一起做学园偶像的时候，我真的很开心。—-WatanabeYou
using namespace std;
typedef long long ll;
const ll boss=1e5;
ll n,i,s,a[boss+10],b[boss+10],k[boss+10],tmp[boss+10];

void merge_sort(ll l,ll r)
{
if (l==r) return;
ll mid=(l+r)>>1,i=l,j=mid+1,p=l;
merge_sort(l,mid),merge_sort(mid+1,r);
for (;i<=mid&&j<=r;a[i]>a[j]?tmp[p++]=a[j++],s+=mid-i+1:tmp[p++]=a[i++]);
while (i<=mid) tmp[p++]=a[i++];
while (j<=r) tmp[p++]=a[j++];
for (i=l;i<=r;i++) a[i]=tmp[i];
}

int main()
{
scanf("%lld",&n);
for (i=1;i<=n;i++) scanf("%lld",&a[i]);
for (i=1;i<=n;i++) scanf("%lld",&b[i]);
for (i=1;i<=n;i++) k[a[i]]=i;
for (i=1;i<=n;i++) a[i]=k[b[i]];
merge_sort(1,n);
printf("%lld",s);
}

65ms,4096kb.length 643.老子不服!

#include<cstdio>
int n,i,a[100010],b[100010],k[100010];long long s;void f(int l,int r){if(l==r)return;int mid=(l+r)>>1,i=l,j=mid+1,p=l;f(l,mid),f(mid+1,r);for(;i<=mid&&j<=r;a[i]>a[j]?b[p++]=a[j++],s+=mid-i+1:b[p++]=a[i++]);while(i<=mid)b[p++]=a[i++];while(j<=r)b[p++]=a[j++];for(i=l;i<=r;i++)a[i]=b[i];}main(){scanf("%d",&n);for(i=1;i<=n;i++)scanf("%d",&a[i]);for(i=1;i<=n;i++)scanf("%d",&b[i]);for(i=1;i<=n;i++)k[a[i]]=i;for(i=1;i<=n;i++)a[i]=k[b[i]];f(1,n);printf("%lld",s);}

50ms,1952kb.length 477.

#include<bits/stdc++.h>
#define boss 100000
using namespace std;
typedef long long ll;
int n,i,a[boss+10],b[boss+10],k[boss+10],tmp[boss+10];
ll s;

inline int read()
{
int x=0;char c=getchar();
for (;!isdigit(c);c=getchar());
for (;isdigit(c);c=getchar()) x=x*10+c-'0';
return x;
}

void merge_sort(int l,int r)
{
if (l==r) return;
int mid=(l+r)>>1,i=l,j=mid+1,p=l;
merge_sort(l,mid),merge_sort(mid+1,r);
for (;i<=mid&&j<=r;a[i]>a[j]?tmp[p++]=a[j++],s+=mid-i+1:tmp[p++]=a[i++]);
while (i<=mid) tmp[p++]=a[i++];
while (j<=r) tmp[p++]=a[j++];
for (i=l;i<=r;i++) a[i]=tmp[i];
}

void write(ll x)
{
if (x>9) write(x/10);
putchar(x%10+'0');
}

int main()
{
n=read();
for (i=1;i<=n;i++) a[i]=read();
for (i=1;i<=n;i++) b[i]=read();
for (i=1;i<=n;i++) k[a[i]]=i;
for (i=1;i<=n;i++) a[i]=k[b[i]];
merge_sort(1,n);
write(s);
}

35ms,2480kb.length 818.

#include<bits/stdc++.h>
#define boss 100000
using namespace std;
typedef long long ll;
int n,i,a[boss+10],k[boss+10];
ll s;

inline int read()
{
int x=0;char c=getchar();
for (;!isdigit(c);c=getchar());
for (;isdigit(c);c=getchar()) x=x*10+c-'0';
return x;
}

void merge_sort(int l,int r)
{
if (l==r) return;
int mid=(l+r)>>1,i=l,j=mid+1,p=l;
merge_sort(l,mid),merge_sort(mid+1,r);
for (;i<=mid&&j<=r;a[i]>a[j]?k[p++]=a[j++],s+=mid-i+1:k[p++]=a[i++]);
while (i<=mid) k[p++]=a[i++];
while (j<=r) k[p++]=a[j++];
for (i=l;i<=r;i++) a[i]=k[i];
}

void write(ll x)
{
if (x>9) write(x/10);
putchar(x%10+'0');
}

int main()
{
int r;
n=read();
for (i=1;i<=n;i++) k[read()]=i;
for (i=1;i<=n;i++) a[i]=k[read()];
merge_sort(1,n);
write(s);
}

37ms,1700kb.length 731.我满意了.
事实证明，千歌对水团其他人都很热情，唯独冷落曜，这果然是一件神奇的事情呢。
再祝凛喵生日快乐。