C85 树状数组+逆序对 P1966 [NOIP2013 提高组] 火柴排队

思路分析：
题目要求将两个火柴队列的高度序列调整为相同，等价于求最少的交换次数使两序列相同。通过排序后建立位置映射，将问题转化为求映射数组的逆序对数量，逆序对数量即为最少交换次数。具体步骤：

1. 对两个数组分别排序，记录排序后的位置；
2. 根据排序后的位置建立映射关系，将问题转化为求映射数组的逆序对；
3. 使用树状数组高效计算逆序对数量，时间复杂度O(n log n)。

// 逆序对+树状数组 O(nlogn)
#include<cstdio>
#include<algorithm>
using namespace std;
#define lowb(x) (x&-x)
const int N=100010, mod=99999997;
struct node 
{
    int val, pos; //值,位置
    bool operator<(node b) {return val<b.val;}
} a[N], b[N];
int n, ans, s[N], c[N]; //c:位置映射
void change(int x, int k) {while(x<=n) s[x]=(s[x]+k)%mod, x+=lowb(x);}
int query(int x) {int t=0;while(x) t=(t+s[x])%mod, x-=lowb(x);return t;}
int main() 
{
    scanf("%d", &n);
    for(int i=1; i<=n; i++)scanf("%d", &a[i].val), a[i].pos=i;
    for(int i=1; i<=n; i++)scanf("%d", &b[i].val), b[i].pos=i;
    sort(a+1, a+n+1);sort(b+1, b+n+1);
    for(int i=1; i<=n; i++) c[a[i].pos] = b[i].pos;
    for(int i=n; i; i--) 
    {
        ans=(ans+query(c[i]-1))%mod;
        change(c[i], 1);
    }
    printf("%d", ans);
    return 0;
}