/*

Author : Slience_K
Belong : C++
Pro : NOIP 2013 - 1 - 2

*/
#include <cstdio>
#include <algorithm>
#define sz 100005
#define LL long long
using namespace std;
struct Node{
int data , pos;
bool operator < ( const Node &x ) const {
return data < x.data;
}
}a[ sz ] , b[ sz ];
const int INF = 99999997;
int n , data[ sz ] , temp[ sz ];
LL ans;
void Merge_sort( int l , int r ){
if ( l >= r ) return;
int mid = ( l + r ) >> 1 , s , t , len = l - 1;
Merge_sort( l , mid );
Merge_sort( mid + 1 , r );
s = l , t = mid + 1;
while( s <= mid && t <= r ){
if ( data[ s ] <= data[ t ] ) temp[ ++len ] = data[ s++ ];
else{

temp[ ++len ] = data[ t ];
ans = ( ans + ( LL )( mid - s + 1 ) ) % INF;
t++;
}
}
while( s <= mid ) temp[ ++len ] = data[ s++ ];
while( t <= r ) temp[ ++len ] = data[ t++ ];
for( int i = l ; i <= r ; i++ )
data[ i ] = temp[ i ];
}
int main(){
freopen( "match.in" , "r" , stdin );
freopen( "match.out" , "w" , stdout );
scanf( "%d" , &n );
for( int i = 1 ; i <= n ; i++ ) {
scanf( "%d" , &a[ i ].data );
a[ i ].pos = i;
b[ i ].pos = i;
}

for( int i = 1 ; i <= n ; i++ )
scanf( "%d" , &b[ i ].data );
sort( a + 1 , a + n + 1 );
sort( b + 1 , b + n + 1 );
for( int i = 1 ; i <= n ; i++ )
b[ i ].data = a[ i ].pos;
sort( b + 1 , b + n + 1 );
for( int i = 1 ; i <= n ; i++ )
data[ i ] = b[ i ].pos;
ans = 0;
Merge_sort( 1 , n );
printf( "%I64d" , ans );
fclose( stdin );
fclose( stdout );
return 0;
}

最后两个题解说的很好 想看题解的直接滚到最后去看吧 其他人写的题解不是很好

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
#define Mod 99999997
#define N 100010
int n;
long long Ans=0;
struct Node{
int value;
int id;
bool operator < (const Node &a) const {
return value<a.value;
}
}A[N],B[N];
int f[N],sum[N];
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
inline int lowbit(int x)
{
return x&(-x);
}
void Update(int x)
{
for(int i=x;i<=n;i+=lowbit(i))
sum[i]++;
}
int Get(int x)
{
int qwer=0;
for(int i=x;i>=1;i-=lowbit(i))
qwer+=sum[i];
return qwer;
}
int main()
{
n=read();
for(int i=1;i<=n;i++)
{
A[i].value=read();
A[i].id=i;
}
for(int i=1;i<=n;i++)
{
B[i].value=read();
B[i].id=i;
}
sort(A+1,A+n+1);
sort(B+1,B+n+1);
for(int i=1;i<=n;i++)
{
f[A[i].id]=B[i].id;
}
for(int i=1;i<=n;i++)
{
Update(f[i]);
Ans=(Ans+i-Get(f[i]))%Mod;
}
cout<<Ans<<endl;
return 0;
}

水水的A了
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

const int mod=99999997;
struct node{ int data,num; };
node temp[150000];
int DiJiDa1[150000],DiJiDa2[150000],hash1[150000],F[150000],tmp[150000];
int i,n,x,ans;

bool cmp(node xx,node yy) { return (xx.data<yy.data); }
/*-----------------------------------------------------------------------------*/
void Prepare()
{
scanf("%d",&n);
for (i=1; i<=n; i++)
{
scanf("%d",&x);
temp[i].data=x;
temp[i].num=i;
}
sort(temp+1,temp+n+1,cmp);
for (i=1; i<=n; i++) DiJiDa1[temp[i].num]=i;
for (i=1; i<=n; i++) hash1[DiJiDa1[i]]=i;

for (i=1; i<=n; i++)
{
scanf("%d",&x);
temp[i].data=x;
temp[i].num=i;
}

sort(temp+1,temp+n+1,cmp);
for (i=1; i<=n; i++) DiJiDa2[temp[i].num]=i;

for (i=1; i<=n; i++) F[i]=hash1[DiJiDa2[i]];
}
/*-----------------------------------------------------------------------------*/
void GB_sort(int L,int mid,int R)
{
int i=L,k=L,j=mid+1;
while ((i<=mid)&&(j<=R))
{
if (F[i]<F[j]) tmp[k++]=F[i++]; else
{
tmp[k++]=F[j++];
ans=((ans%mod)+((mid-i+1)%mod))%mod;
}

}
while(i<=mid) tmp[k++]=F[i++];
while(j<=R) tmp[k++]=F[j++];
for(int p=L; p<=R; p++) F[p]=tmp[p];

}
/*-----------------------------------------------------------------------------*/
void GB(int L,int R)
{
if (L<R)
{
int mid=(L+R)/2;
GB(L,mid);
GB(mid+1,R);
GB_sort(L,mid,R);
}
}
/*-----------------------------------------------------------------------------*/

int main()
{
Prepare();
GB(1,n);
cout<<ans<<endl;
}

测试数据 #0: Accepted, time = 15 ms, mem = 3656 KiB, score = 10
测试数据 #1: Accepted, time = 1 ms, mem = 3660 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 3656 KiB, score = 10
测试数据 #3: Accepted, time = 9 ms, mem = 3660 KiB, score = 10
测试数据 #4: Accepted, time = 15 ms, mem = 3660 KiB, score = 10
测试数据 #5: Accepted, time = 46 ms, mem = 3660 KiB, score = 10
测试数据 #6: Accepted, time = 106 ms, mem = 3656 KiB, score = 10
测试数据 #7: Accepted, time = 187 ms, mem = 3656 KiB, score = 10
测试数据 #8: Accepted, time = 484 ms, mem = 3660 KiB, score = 10
测试数据 #9: Accepted, time = 765 ms, mem = 3660 KiB, score = 10
Accepted, time = 1628 ms, mem = 3660 KiB, score = 100

Code

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

#define MAXN 100005
#define MOD 99999997
int n,id[MAXN],_id[MAXN];
long long ans;
struct Match { int val,id,seq;} a[MAXN],b[MAXN];

bool cmp1(Match A,Match B) { return A.val<B.val;}
bool cmp2(Match A,Match B) { return A.seq<B.seq;}

void Merge(int b1,int e1,int b2,int e2)
{
int bgn=b1,end=e2;
int p=b1;
while(b1<=e1 && b2<=e2)
{
if(id[b1]<id[b2]) { _id[p++]=id[b1++]; continue;}
if(id[b1]>id[b2]) { _id[p++]=id[b2++]; ans+=(e1-b1+1); ans%=MOD; continue;}
}
if(b1>e1) while(b2<=e2) _id[p++]=id[b2++];
if(b2>e2) while(b1<=e1) _id[p++]=id[b1++];

for(int i=bgn;i<=end;i++)
id[i]=_id[i];
}

void mergesort(int l,int r)
{
if(l<r)
{
int div=(l+r)/2;
mergesort(l,div);
mergesort(div+1,r);
Merge(l,div,div+1,r);

}
}

int main()
{
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i].val, a[i].seq=i;
for(int i=1;i<=n;i++) cin>>b[i].val, b[i].seq=i;
sort(a+1,a+n+1,cmp1);
sort(b+1,b+n+1,cmp1);
for(int i=1;i<=n;i++) b[i].id=a[i].seq;
//sort(a+1,a+n+1,cmp2);
sort(b+1,b+n+1,cmp2);
for(int i=1;i<=n;i++) id[i]=b[i].id;
mergesort(1,n);
cout<<ans%MOD<<endl;
return 0;
}

先贪心 确定两个数组数字的对应关系 然后整合成一个数组 求数组中的逆序对个数 由于n可能到达100000的数据规模 需要Nlogn的复杂度 可以用树状数组或者归并排序的思想解决。其实n^2的算法由于数据生成随机也是有70分的。Orz

记录信息
评测状态 Accepted
题目 P1842 火柴排队
递交时间 2014-10-26 15:49:23
代码语言 C++
评测机 上海红茶馆
消耗时间 654 ms
消耗内存 2900 KiB
评测时间 2014-10-26 15:49:24
评测结果
编译成功
测试数据 #0: Accepted, time = 15 ms, mem = 2892 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 2896 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 2896 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 2892 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 2896 KiB, score = 10
测试数据 #5: Accepted, time = 15 ms, mem = 2900 KiB, score = 10
测试数据 #6: Accepted, time = 31 ms, mem = 2896 KiB, score = 10
测试数据 #7: Accepted, time = 78 ms, mem = 2892 KiB, score = 10
测试数据 #8: Accepted, time = 187 ms, mem = 2896 KiB, score = 10
测试数据 #9: Accepted, time = 328 ms, mem = 2896 KiB, score = 10
Accepted, time = 654 ms, mem = 2900 KiB, score = 100
代码
#include<iostream>
#include<algorithm>
#include<queue>
#include<string>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<cmath>
#include<cctype>
#define FOR(a,b) for(int i=a;i<=b;i++)
using namespace std;
struct hc
{
int num;
int bh;
}a[100001],b[100001];
int n,ans=0;
int c[100001];
int tmp[100001];
bool hcsort(const hc &a,const hc &b)
{
return a.num<b.num;
}
void init()
{
FOR(1,n)
{
cin>>a[i].num;
a[i].bh=i;
}
FOR(1,n)
{
cin>>b[i].num;
b[i].bh=i;
}
}
void first()
{
sort(a+1,a+n+1,hcsort);
sort(b+1,b+n+1,hcsort);
FOR(1,n)
c[a[i].bh]=b[i].bh;
}
void gbsort(int l,int m,int r)
{
int k=l;
int lp=l;
int rp=m+1;
while(lp<=m&&rp<=r)
{
if(c[lp]>c[rp])
{
tmp[k++]=c[rp++];
ans=(ans+(m-lp+1))%99999997;
}
else
{
tmp[k++]=c[lp++];
}
}
FOR(lp,m) tmp[k++]=c[i];
FOR(rp,r) tmp[k++]=c[i];
FOR(l,r) c[i]=tmp[i];
}
void gb(int l,int r)
{
int m=(l+r)/2;
if(l<r)
{
gb(l,m);
gb(m+1,r);
gbsort(l,m,r);
}
}
int main()
{
ios::sync_with_stdio(false);
cin>>n;
init();
first();
gb(1,n);
cout<<ans;
return 0;
}

###code
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <climits>
using namespace std;
int data1[1000000+5],data2[1000000+5],p1[1000000+5],p2[1000000+5],temp[100000+5];
int len=0;
int cnt=0;
void mange(int,int,int);
void mangesort(int,int);
struct pii
{
int x;
int y;
bool operator <(const pii m) const
{
return x<m.x;
}
bool operator ==(const pii m) const
{
return x==m.x;
}
};
pii l[1000000+5];
int main()
{ cin>>len;
for(int i=0;i!=len;++i)
scanf("%d",&data1[i]);
for(int i=0;i!=len;++i)
scanf("%d",&data2[i]);
memcpy(temp,data1,sizeof(int)*len);
sort(temp,temp+len);
for(int i=0;i!=len;++i)
data1[i]=lower_bound(temp,temp+len,data1[i])-temp;
memcpy(temp,data2,sizeof(int)*len);
sort(temp,temp+len);
for(int i=0;i!=len;++i)
data2[i]=lower_bound(temp,temp+len,data2[i])-temp;
for(int i=0;i!=len;++i)
{
pii t;
t.x=data2[i];
t.y=i;
l[i]=t;
}
sort(l,l+len);
for(int i=0;i!=len;++i)
{
pii t;
t.x=data1[i];
t.y=0;
int p=lower_bound(l,l+len,t)-l;
data1[i]=l[p].y;
}
mangesort(0,len-1);
cout<<cnt<<endl;
return 0;
}

void mangesort(int l,int r)
{
if(l<r)
{
int p=(l+r)/2;
mangesort(l,p);
mangesort(p+1,r);
mange(l,p,r);
}
}

void mange(int l,int p,int r)
{
int n1=p-l+1;
int n2=r-p;
int x=0;
int *L=new int[n1+1];
int *R=new int[n2+1];
for(int i=l;i<=p;++i)
L[x++]=data1[i];
x=0;
for(int i=p+1;i<=r;++i)
R[x++]=data1[i];
L[n1]=INT_MAX;
R[n2]=INT_MAX;
int px=0,py=0;
for(int i=l;i<=r;++i)
if(L[px]<R[py]) data1[i]=L[px++];
else
{
data1[i]=R[py++];
cnt+=n1-px;
cnt%=99999997;
}
}

//我是SkyDec大爷的脑残粉~~
离散写得丑请无视~
想复习一下归并所以没有写树状数组……

#include<cstdio>
#include<algorithm>
using namespace std;

const int Maxn=100000+19,Mod=99999997;
struct note {int a,num;} A[Maxn],B[Maxn];
int n,C[Maxn],rank[Maxn],tmp[Maxn],Ans;

inline int cmp1(note A,note B) {return A.a<B.a;}
inline int cmp2(note A,note B) {return A.num<B.num;}
inline void Merge_sort(int L,int R)
{
if (L==R) return;
int Mid=(L+R)>>1;
Merge_sort(L,Mid);
Merge_sort(Mid+1,R);
int tl=L,tr=Mid+1,now=L;
while (tl<=Mid&&tr<=R)
{
if (C[tl]<C[tr]) tmp[now++]=C[tl++];
else
{
tmp[now++]=C[tr++];
(Ans+=Mid-tl+1)%=Mod;
}
}
while (tl<=Mid) tmp[now++]=C[tl++];
while (tr<=R) tmp[now++]=C[tr++];
for (int i=L;i<=R;i++) C[i]=tmp[i];
}

int main()
{
scanf("%d",&n);
for (int i=0;i<n;i++) scanf("%d",&A[i].a),A[i].num=i;
for (int i=0;i<n;i++) scanf("%d",&B[i].a),B[i].num=i;
sort(A,A+n,cmp1);sort(B,B+n,cmp1);
for (int i=0;i<n;i++) A[i].a=B[i].a=i;
sort(A,A+n,cmp2);sort(B,B+n,cmp2);
for (int i=0;i<n;i++) rank[A[i].a]=i;
for (int i=0;i<n;i++) C[i]=rank[B[i].a];
Merge_sort(0,n-1);
printf("%d\n",Ans);
}

#include<iostream>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>

#define M 101011
#define MOD 99999997
#define INF 0x7fffffff

using namespace std;

int n;
int a[M],b[M];
int f[M];
int flag[M];
struct node
{
int w;
int no;
}str1[M],str2[M];

struct node1
{
int a;
int b;
int num;
}str3[M],str4[M];

int cmp(const node &a,const node &b)
{
return a.w<b.w;
}

int cmp1(const node1 &a,const node1 &b)
{
return a.a<b.a;
}

int cmp2(const node1 &a,const node1 &b)
{
return a.b>b.b;
}

void init()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
int x;
scanf("%d",&x);
str1[i].w=x;
str1[i].no=i;
}
for(int i=1;i<=n;i++)
{
int x;
scanf("%d",&x);
str2[i].w=x;
str2[i].no=i;
}
sort(str1+1,str1+n+1,cmp);
sort(str2+1,str2+n+1,cmp);
for(int i=1;i<=n;i++)
{
str3[i].a=str1[i].no;
str3[i].b=str2[i].no;
}
sort(str3+1,str3+n+1,cmp1);
for(int i=1;i<=n;i++)
str3[i].num=i;
for(int i=1;i<=n;i++)
str4[i]=str3[i];
sort(str4+1,str4+n+1,cmp2);
for(int i=1;i<=n;i++)
flag[i]=str4[i].num;
}

int lowbit(int x)
{
return x&(-x);
}

void add(int x,int w)
{
while(x<=n)
{
f[x]+=w;
x+=lowbit(x);
}
}

int getsum(int x)
{
int res=0;
while(x>0)
{
res+=f[x];
x-=lowbit(x);
}
return res;
}

void start()
{
for(int i=1;i<=n;i++)
f[i]=0;
int sum=0;
for(int i=1;i<=n;i++)
{
add(flag[i],1);
sum=(sum+getsum(flag[i]-1))%MOD;
}
printf("%d\n",sum);
}

int main()
{
init();
start();
return 0;
}

###为什么只有80分啊……
#include <iostream>
#include <cstring>
using namespace std;
long c[100001],d[100001];
long s=0;
void Qsort(long l,long r)
{
long i,j,k,mid;
mid=c[(l+r)/2];
i=l; j=r;
while (i<=j){
while (c[i]<mid) i++;
while (c[j]>mid) j--;
if (i<=j){
k=c[i];
c[i]=c[j];
c[j]=k;
k=d[i];
d[i]=d[j];
d[j]=k;
i++;
j--;
}

}
if (l<j) Qsort(l,j);
if (i<r) Qsort(i,r);
}
void sort(long l,long mid,long r)
{
long i,j,k;
for (i=l;i<=mid;i++)
for (j=r;j>=mid+1;j--){
if (c[i]>c[j]){
s=(s+j-mid)%99999997;
break;
}
}
i=l;
j=mid+1;
for (k=l;k<=r;k++){
if ((c[i]<c[j] && i<=mid) || (j>r)){
d[k]=c[i];
i++;
}else {
d[k]=c[j];
j++;
}
}
for (i=l;i<=r;i++)
c[i]=d[i];
}
void merge(long l,long r)
{
long mid;
mid=(l+r)/2;
if (l<mid) merge(l,mid);
if (mid+1<r) merge(mid+1,r);
sort(l,mid,r);
}
main()
{
long a1[100001],a2[100001],b1[100001],b2[100001],i,j,n;
cin>>n;
for (i=1;i<=n;i++){
cin>>a1[i];
b1[i]=b2[i]=i;
}
for (i=1;i<=n;i++) cin>>a2[i];
memcpy(c,a1,sizeof(a1)); memcpy(d,b1,sizeof(b1));
Qsort(1,n);
memcpy(a1,c,sizeof(a1)); memcpy(b1,d,sizeof(b1));
memcpy(c,a2,sizeof(a2)); memcpy(d,b2,sizeof(b2));
Qsort(1,n);
memcpy(a2,c,sizeof(a2)); memcpy(b2,d,sizeof(b1));
for (i=1;i<=n;i++){
a1[b1[i]]=i; a2[b2[i]]=i;
}
for (i=1;i<=n;i++)
for (j=1;j<=n;j++)
if (a1[i]==a2[j]){ a1[i]=j; break;}
memcpy(c,a1,sizeof(c));
merge(1,n);
cout<<s;
}

为什么只有80分啊……
#include <iostream>
#include <cstring>
using namespace std;
long c[100001],d[100001];
long s=0;
void Qsort(long l,long r)
{
long i,j,k,mid;
mid=c[(l+r)/2];
i=l; j=r;
while (i<=j){
while (c[i]<mid) i++;
while (c[j]>mid) j--;
if (i<=j){
k=c[i];
c[i]=c[j];
c[j]=k;
k=d[i];
d[i]=d[j];
d[j]=k;
i++;
j--;
}

}
if (l<j) Qsort(l,j);
if (i<r) Qsort(i,r);
}
void sort(long l,long mid,long r)
{
long i,j,k;
for (i=l;i<=mid;i++)
for (j=r;j>=mid+1;j--){
if (c[i]>c[j]){
s=(s+j-mid)%99999997;
break;
}
}
i=l;
j=mid+1;
for (k=l;k<=r;k++){
if ((c[i]<c[j] && i<=mid) || (j>r)){
d[k]=c[i];
i++;
}else {
d[k]=c[j];
j++;
}
}
for (i=l;i<=r;i++)
c[i]=d[i];
}
void merge(long l,long r)
{
long mid;
mid=(l+r)/2;
if (l<mid) merge(l,mid);
if (mid+1<r) merge(mid+1,r);
sort(l,mid,r);
}
main()
{
long a1[100001],a2[100001],b1[100001],b2[100001],i,j,n;
cin>>n;
for (i=1;i<=n;i++){
cin>>a1[i];
b1[i]=b2[i]=i;
}
for (i=1;i<=n;i++) cin>>a2[i];
memcpy(c,a1,sizeof(a1)); memcpy(d,b1,sizeof(b1));
Qsort(1,n);
memcpy(a1,c,sizeof(a1)); memcpy(b1,d,sizeof(b1));
memcpy(c,a2,sizeof(a2)); memcpy(d,b2,sizeof(b2));
Qsort(1,n);
memcpy(a2,c,sizeof(a2)); memcpy(b2,d,sizeof(b1));
for (i=1;i<=n;i++){
a1[b1[i]]=i; a2[b2[i]]=i;
}
for (i=1;i<=n;i++)
for (j=1;j<=n;j++)
if (a1[i]==a2[j]){ a1[i]=j; break;}
memcpy(c,a1,sizeof(c));
merge(1,n);
cout<<s;
}

代码奇短无比。
楼下的skydec大爷说的很明白了。
第一次交WA了，发现ans没开long long。
第二次交又WA了，发现没取模。
#include<cstdio>
#include<map>
#define L(x) (x&-x)
using namespace std;
map<int,int>Map;
int f[1000005],n,x,i,now;long long ans=0;
inline void add(int x) {for (;x<=n;x+=L(x)) f[x]++;}
inline int ask(int x) {int s=0;for (;x;x-=L(x)) s+=f[x];return s;}

int main()
{
scanf("%d",&n);
for (i=1;i<=n;i++)
scanf("%d",&x),Map[x]=i;
for (i=1;i<=n;i++)
{
scanf("%d",&x);now=Map[x];
ans+=(long long)(i-1-ask(now));
add(now);
}
printf("%I64d",ans%99999997);
return 0;
}

var a,b,c:array[0..100000]of longint;
n,i,ans:longint;
procedure ex(var x,y:longint);
var t:longint;begin t:=x;x:=y;y:=t;end;
procedure qs(l,r:longint);
var i,j,m:longint;
begin
if l>=r then exit;
i:=l;j:=r;m:=a[(i+j)>>1];
repeat
while a[i]<m do inc(i);
while a[j]>m do dec(j);
if i<=j then begin
ex(a[i],a[j]);
ex(c[i],c[j]);
inc(i);dec(j);
end;
until i>j;
qs(l,j);qs(i,r);
end;
function lb(k:longint):longint;
begin exit(k and (-k));end;
function sum(k:longint):longint;
begin
sum:=0;
while k>0 do begin
inc(sum,b[k]);
dec(k,lb(k));
end;
end;
procedure undata(k:longint);
begin
while k<=n do begin
inc(b[k]);
inc(k,lb(k));
end;
end;
begin
readln(n);
for i:=1 to n do begin read(a[i]);c[i]:=i;end;
qs(1,n);
b:=c;
for i:=1 to n do begin read(a[i]);c[i]:=i;end;
qs(1,n);
for i:=1 to n do a[b[i]]:=c[i];
fillchar(b,sizeof(b),0);
for i:=1 to n do begin
undata(a[i]);
inc(ans,i-sum(a[i]));
ans:=ans mod 99999997;
end;
writeln(ans);
end.

用归并，预处理用数组hash。
for i:=1 to n do f[a[i]]:=i;
for i:=1 to n do a[i]:=f[aa[i]];
for i:=1 to n do f[b[i]]:=i;
for i:=1 to n do b[i]:=f[bb[i]];

来之不易啊 一下午+一晚上
const w=99999997;
type arr=array[1..100000] of longint;
var a,b,c,d,key,g:arr;
i,n:longint;
ans:int64;
procedure merge(var a:arr;left,p,right:longint);
var
i,j,k:longint;
tmp:arr;
begin
i:=left; j:=p+1; k:=left;
while (i<=p) and (j<=right) do
begin
if a[i]<=a[j] then
begin tmp[k]:=a[i]; inc(i); end
else
begin tmp[k]:=a[j]; ans:=ans+p-i+1; inc(j); end;
inc(k);
end;
while i<=p do
begin tmp[k]:=a[i];inc(i);inc(k);end;
while j<=right do
begin tmp[k]:=a[j];inc(j);inc(k);end;
for i:=left to right do
a[i]:=tmp[i];
end;
procedure mergesort(var a:arr;left,right:longint);
var
mid:longint;
begin
if left<right then
begin
mid:=(left+right) div 2;
mergesort(a,left,mid);
mergesort(a,mid+1,right);
merge(a,left,mid,right);
end;
end;
procedure qsort(var a:arr;h,l:longint);
var i,j,m,temp:longint;
begin
i:=h;j:=l;m:=a[(i+j) div 2];
repeat
while a[i]<m do inc(i);
while a[j]>m do dec(j);
if i<=j then
begin
temp:=a[i];a[i]:=a[j];a[j]:=temp;
temp:=g[i];g[i]:=g[j];g[j]:=temp;
inc(i);dec(j);
end;
until i>j;
if i<l then qsort(a,i,l);
if j>h then qsort(a,h,j);
end;
begin
readln(n);
for i:=1 to n do read(c[i]);
readln;
for i:=1 to n do read(d[i]);
for i:=1 to n do g[i]:=i;
qsort(c,1,n);
for i:=1 to n do c[g[i]]:=i;
for i:=1 to n do g[i]:=i;
qsort(d,1,n);
for i:=1 to n do d[g[i]]:=i;
for i:=1 to n do key[d[i]]:=i;
for i:=1 to n do c[i]:=key[c[i]];
ans:=0;
mergesort(c,1,n);
writeln(ans mod w);
end.

用 BIT 实现的逆序对
什么你要题解？楼下两位已经说得很明白了~

#include <stdio.h>
#include <stdlib.h>

#define MAXN 100010
#define lowbit(x) (x & (-x))

typedef struct {
int data, no;
} node;

node a[MAXN], b[MAXN];
int tr[MAXN], c[MAXN];
int n;

int cmp(const void *a, const void *b) {
node *aa = (node *)a;
node *bb = (node *)b;
if (aa->data == bb->data) {
return (aa->no - bb->no);
} else {
return (aa->data - bb->data);
}
}

void update(int p, int value) {
int i;

for(i = p; i <= n; i += lowbit(i)) {
tr[i] += value;
}
}

int getsum(int p) {
int i, tmp = 0;

for (i = p; i > 0; i -= lowbit(i)) {
tmp += tr[i];
}
return tmp;
}

int main() {
int i, ans = 0;

scanf("%d", &n);
for (i = 0; i < n; i++) {
scanf("%d", &a[i].data);
a[i].no = i + 1;
}
for (i = 0; i < n; i++) {
scanf("%d", &b[i].data);
b[i].no = i + 1;
}
qsort(a, n, sizeof(a[0]), cmp);
qsort(b, n, sizeof(b[0]), cmp);
for (i = 0; i < n; i++) {
c[b[i].no] = a[i].no;
}
for (i = 1; i <= n; i++) {
update(c[i], 1);
ans = (ans + i - getsum(c[i])) % 99999997;
}
printf("%d\n", ans);
return 0;
}

首先把那个式子拆开，用排序不等式貌似可以发现最小值就是先对两个火柴的高度a[],b[]排序，然后对于每一个a[i]，只要跟b[i]在一起就是最小的。
所以我们要做的工作就剩下计算移动量。
弱菜没想到逆序对，更没想到归并排序...直接模拟，我们从1到n，对于每一个a[i]，找到其排序后对应的b[k]，显然我们可以不动a[i]，只移动b[k]到b[i]处，这样子显然是步数最小的。所以答案就加上k-i，但是移动之后b[k]之前的,b[i]之后的点的坐标都会加1，这个看起来就像树状数组的区间加减，然后每一次只要求单点的值就可以了...然后咱就用树状数组维护每一次移动之后所有点应该在的位置。这样子复杂度就是O(NlogN)的.....