P3656 [USACO17FEB] Why Did the Cow Cross the Road I P

思路

首先，$A$ 和 $B$ 只会移动一个，那么，我们分开来算，我们先假定 $B$ 会动。

不妨令 $A$ 与 $b$ 连边的端点为 $x,y$。如果有线段 $pq$ 能与 $xy$ 相交，一定满足如下其中一条规律：

1. $p < x \wedge q > y$
2. $p > x \wedge q < y$

发现每一次循环右移一次，只会影响一条端点在 $B_n$ 的位置的线段，其余线段相对位置不变。

令 $B_n$ 在 $A$ 中的位置为 $x$。因为 $B_n$ 是在 $B$ 中的最后一个元素，所以如果有线段能与其所在线段相交，那么只能是满足上述规律中的第 2 种。所以所有以 $A_{x + 1 \sim n}$ 为端点的线段一定与 $B_n$ 所在线段相交。

那么，如果我们将 $B$ 循环右移一位后，可以发现原本与 $B_n$ 相交的线段都不会相交了，即将数量 $res$ 变为了 $res - (n - x)$。

再来考虑 $B_n$ 循环右移到 $B_1$ 时会产生新的数量。因为 $B_1$ 是 $B$ 中的第一个元素，所以如果有线段能与其所在线段相交，那么只能是满足上述条件中的第 1 种。所以，所有以 $A_{1 \sim x - 1}$ 为端点的线段一定与其相交。

那么，我们将 $B$ 循环右移一位后，可以发现能新产生 $x - 1$ 条线段，即将数量 $res$ 变为了 $res + (x - 1)$。

那么结果 $res$ 将变为 $res - (n - x) + (x - 1) = res - n + 2x - 1$。

接下来只需要处理出 $res$ 在不动时的结果即可。

我们将 $pos_i$ 表示 $B$ 在 $A$ 中的位置，可以发现当 $i < j \wedge pos_i > pos_j$ 时就会产生一条相交的线段对。然后发现本质上就是求 $pos$ 的逆序对数量，用树状数组算一下即可。

注意：不要忘了讨论 $A$ 动的情况。

Code

#include <bits/stdc++.h>  
#define re register  
#define int long long  
  
using namespace std;  
  
const int N = 1e5 + 10;  
int n,ans,t;  
int arr[N],brr[N],vis[N],pos[N];  
  
inline int read(){  
    int r = 0,w = 1;  
    char c = getchar();  
    while (c < '0' || c > '9'){  
        if (c == '-') w = -1;  
        c = getchar();  
    }  
    while (c >= '0' && c <= '9'){  
        r = (r << 3) + (r << 1) + (c ^ 48);  
        c = getchar();  
    }  
    return r * w;  
}  
  
struct BIT{  
    int tr[N];  
  
    inline int lowbit(int x){  
        return x & -x;  
    }  
  
    inline void modify(int x,int k){  
        for (re int i = x;i <= n;i += lowbit(i)) tr[i] += k;  
    }  
  
    inline int query(int x){  
        int res = 0;  
        for (re int i = x;i;i -= lowbit(i)) res += tr[i];  
        return res;  
    }  
}tree;  
  
inline int f(int *arr,int *brr){  
    for (re int i = 1;i <= n;i++) vis[arr[i]] = i;  
    for (re int i = 1;i <= n;i++) pos[i] = vis[brr[i]];  
    int res = 0,ans = 0;  
    memset(tree.tr,0,sizeof(tree.tr));  
    for (re int i = n;i;i--){  
        res += tree.query(pos[i]);  
        tree.modify(pos[i],1);  
    }  
    ans = res;  
    for (re int i = n;i;i--){  
        res = res - n + 2 * pos[i] - 1;  
        ans = min(ans,res);  
    }  
    return ans;  
}  
  
signed main(){  
    n = read();  
    for (re int i = 1;i <= n;i++) arr[i] = read();  
    for (re int i = 1;i <= n;i++) brr[i] = read();  
    printf("%lld",min(f(arr,brr),f(brr,arr)));  
    return 0;  
}