这道题在处理上还是稍微有点麻烦的……
可以想到，如果使两列火柴距离差值最小，肯定是每列火柴排名第k高的对应的在同一位置。这样的话，如果我们把第二列火柴映射为其出现在第一列火柴中的位置，我们只要求一下映射之后的逆序对数即可。
不过不能直接映射，因为有些数并不是公共的，所以我们先把两个序列都先离散一遍，之后这两个序列就成了1～n的全排列之中的两种，我的做法是记录a序列中所有元素的位置，之后sort一遍，就能直接求出来b序列中的元素在a中的位置是哪了。
最后用树状数组求一下逆序对就可以啦。注意别忘了取模……
看一下代码。
#include<cstdio> #include<algorithm> #include<cstring> #include<iostream> #include<cmath> #include<set> #include<queue> #define lowbit(x) x & (-x) #define rep(i,a,n) for(int i = a;i <= n;i++) #define per(i,n,a) for(int i = n;i >= a;i--) #define enter putchar(' ') using namespace std; typedef long long ll; const int M = 1000005; const int N = 2005; const ll INF = 1e17+9; const ll mod = 99999997; ll read() { ll ans = 0,op = 1; char ch = getchar(); while(ch < '0' || ch > '9') { if(ch == '-') op = -1; ch = getchar(); } while(ch >= '0' && ch <= '9') { ans *= 10; ans += ch - '0'; ans %= mod; ch = getchar(); } return ans * op; } struct node { ll pos,val; bool operator < (const node &g) const { return val < g.val; } }a[M]; ll n,b[M],c[M],d[M],tot1,tot2,g[M],e[M],ans; void add(ll x) { while(x <= M-2) { g[x]++; if(g[x] >= mod) g[x] -= mod; x += lowbit(x); } } ll ask(ll x) { ll cur = 0; while(x) { cur += g[x],x -= lowbit(x); if(cur >= mod) cur -= mod; } return cur; } int main() { n = read(); rep(i,1,n) a[i].val = read(),c[i] = a[i].val,a[i].pos = i; rep(i,1,n) b[i] = read(),d[i] = b[i]; sort(c+1,c+1+n); rep(i,1,n) a[i].val = lower_bound(c+1,c+1+n,a[i].val) - c; sort(d+1,d+1+n); rep(i,1,n) b[i] = lower_bound(d+1,d+1+n,b[i]) - d; sort(a+1,a+1+n); //rep(i,1,n) printf("^%lld ",a[i].val);enter; //rep(i,1,n) printf("^%lld ",b[i]);enter; per(i,n,1) { b[i] = a[b[i]].pos; ans += ask(b[i]-1); if(ans >= mod) ans -= mod; add(b[i]); } printf("%lld ",ans % mod); return 0; }