题目：https://www.luogu.org/problemnew/show/P1966
首先，一个排列相邻交换变成另一个排列的交换次数就是逆序对数；
随便画一画，感觉应该是排个序，大的对应大的，小的对应小的差值最小，具体证明的话应该是分类讨论一下吧；
操作两个序列可以转化成操作一个序列，大小对应就行了；
差点被 rk[] , ps[] 什么的弄晕，还是因为懒不想写离散化...
总之1A还是蛮高兴的。
代码如下：
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; typedef long long ll; int const maxn=1e5+5,mod=99999997; int n,psb[maxn],rkb[maxn],f[maxn],rka[maxn]; ll ans,a[maxn],b[maxn]; ll rd() { ll ret=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();} while(ch>='0'&&ch<='9')ret=ret*10+ch-'0',ch=getchar(); return ret*f; } bool cmp1(int x,int y){return a[x]>a[y];} bool cmp2(int x,int y){return b[x]>b[y];} void add(int x){for(;x;x-=(x&-x))f[x]++;} int query(int x){int ret=0; for(;x<=n;x+=(x&-x))ret+=f[x]; return ret;} int main() { n=rd(); for(int i=1;i<=n;i++)a[i]=rd(),rka[i]=i; for(int i=1;i<=n;i++)b[i]=rd(),rkb[i]=i; sort(rka+1,rka+n+1,cmp1); sort(rkb+1,rkb+n+1,cmp2); // for(int i=1;i<=n;i++)printf("rka[%d]=%d rkb[%d]=%d ",i,rka[i],i,rkb[i]); for(int i=1;i<=n;i++)psb[rkb[i]]=i; for(int i=1;i<=n;i++) { int ps=rka[psb[i]]; ans=(ans+query(ps))%mod; add(ps); } printf("%lld ",ans); return 0; }