好吧，我们上次说这道题可以用归并排序做。。
但是我不会归并排序的锅（真是蒟蒻。。）
早晨爬起来赶紧学一发。。
貌似还挺简单的。。
233~
好吧，切入正题。
归并排序其实就是利用了分治的思想。
分治：将一个大问题分为2个小问题，之后解决所有的小问题，再合并答案。
比如我们举一个数列，对它进行归并排序。
a[10]={9,2,3,5,4,6,6,7,9,5}
归并的顺序是这样的
{9,2,3,5,4}{6,6,7,9,5};
{9,2,3}{5,4}{6,6,7}{9,5};
{9,2}{3}{5,4}{6,6}{7}{9,5}
分到这一步后，有2种方法：
第一是继续分，然后归并，第二是不分，然后判断一下2个数的大小关系，如{9 2}变为{2 9}然后归并。。（其实复杂度差不多，就是少几个常数。。）
合并过程：（接上表）
{2,9}{3}{4 5}{6 6}{7}{5 9}
{2,3,9}{4,5}{6,6,7}{5,9}
{2,3,4,5,9}{5,6,6,7,9}
{2,3,4,5,5,6,6,7,9,9}
恩，就是这样。
合并的代码实现就是将2块数组放2个指针。
逐一扫描，比较。
然后把结果重新放回原数组中
好吧，感觉讲的不是很清楚。
然后逆序对的个数呢，是这样的；
在归并排序中
假设我们要合并2个有序的数列a1,a2
那么假设a1中left<=i<=mid
a2中mid<j<=right
如果a1[i]>=a2[j]
那么a1[k](i<=k<=mid)一定>a2[j]
所以逆序对（也就是ans）+=mid-i+1;(+1是因为包括i本身也是逆序对)
还是上代码吧。。
#include<iostream> #include<cstdio> #include<algorithm> #define mod 99999997 using namespace std; struct lisan{ int opt,value; }a[100001],b[100001]; int result[100001],c[100001],d[100001],ans,n; bool cmp(lisan a,lisan b){ return a.value<b.value;} void mergesort(int left,int right){ if(left>=right)return ; int mid=(left+right)>>1,i,j,k; mergesort(left,mid); mergesort(mid+1,right); for(i=left,j=mid+1,k=left;i<=mid&&j<=right;k++) { if(c[i]<c[j])d[k]=c[i++]; else ans+=mid-i+1,ans%=mod,d[k]=c[j++]; } while(i<=mid) d[k++]=c[i++]; while(j<=right) d[k++]=c[j++]; for(i=left;i<=right;i++) c[i]=d[i]; } int main(){ scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d",&a[i].value); a[i].opt=i; } for(int i=1;i<=n;i++) { scanf("%d",&b[i].value); b[i].opt=i; } sort(a+1,a+n+1,cmp); sort(b+1,b+n+1,cmp); for(int i=1;i<=n;i++) c[b[i].opt]=a[i].opt; mergesort(1,n); printf("%d",ans); }
比树状数组快诶。（树状数组背锅。。）
其实都是O（nlogn）只不过常数小了点。
恩，就是这样。
线段树算法和乱七八糟的算法还是去死吧。。（等我成为蒟蒻中的巨神再回来补。。）