【题解】[USACO17FEB] Why Did the Cow Cross the Road I (P) By 5ab as a juruo.

题目信息
分析
注意事项
Code

题目信息

题目来源：USACO 2017 February 铂金组 T1；

运行限制：(1.00 extrm{s})，(128 extrm{MiB})。

题目描述

为什么牛要过马路？我们可能永远都不知道全部原因，但肯定的是，FJ 的牛经常穿过马路。事实上，他们经常过马路，当他们的路径交叉时，他们经常碰到对方，这是 FJ 希望改进的情况。

FJ 将奶牛分成了 (N) 个不同的品种，他的每一个田地都是专门为一种特定的品种放牧。例如，专门用于品种 12 奶牛的田地只能用于品种 12 的奶牛，而不能用于任何其他品种的奶牛。一条长长的路穿过他的农场。道路一侧有 (N) 个田地（每个品种一个），道路另一侧也有 (N) 个田地（每个品种也有一个）。所以，当一头牛穿过马路，它会穿过特定品种的两个田地。

如果 FJ 更仔细的研究他的计划，他会在道路两旁订购同品种田地，所以每个品种的两个田野将直接穿过彼此的道路。这样就可以让奶牛随意过马路，而不会有不同品种的牛碰撞在一起。唉，但现在道路两边的田地可能不一样，所以 FJ 明白，可能会有一对品种 ((a,b)) 是交叉的当且仅当是一对不同的品种，且道路上一边田地品种 (a) 上的任何路线都与道路另一边田地品种 (b) 的任何路线相交。

FJ 希望尽量减少品种的交叉对数。由于物流方面的原因，他表示，他可以在道路的一边移动牛，所以那边的田地可以「循环转移」。也就是说，对于一个给定的常值 (k) 来说，循环转移是指每头牧场里的牛都会向前移动 (k) 个田野，而最前面的 (k) 只奶牛会移动到最后，因为向前移动的奶牛已经填补了前k个田地。比如，如果道路一侧的田地移动前的排列为 (left<3,7,1,2,5,4,6 ight>)，假设 (k=2)，新排列将为 (left<4,6,3,7,1,2,5 ight>)。

请编程确定在道路一侧的田野适当循环移动后存在的品种交叉对的最小值。（可以选择在两侧任意一边进行）

输入格式

第一行包含 (N)。

接下来 (N) 行按顺序描述了小路一旁田地的品种的 ID 号，每一个 ID 号是一个在 (1cdots N) 之间的整数。

倒数 (N) 行描述了小路另一旁田地的品种的 ID 号。

输出格式

循环移动道路侧的田野后，请输出可能的品种交叉对的最小数量。

数据规模与约定

(1le Nle 10^5)。

分析

题意是说给你两个 (1) 到 (n) 的排列，对其中的一个进行适当的调整，使得相等的数之间的连线的交点最少（不考虑共点），输出这个值。

使排列之间相等的数之间的连线的交点最少，这是一个比较裸的逆序对问题，可以 (mathcal{O}(Nlog N)) 完成。

但是，由于这个问题存在修改操作（可以这么理解），所以复杂度会达到 (mathcal{O}(N^2log N))，无法满分。怎么应对修改操作呢？

我们可以考虑像 DP 那样快速转移。观察改变后交叉点数量的变化情况，会有如下发现：

所以，我们只需要维护对应的品种在何处即可。这样转一次就是 (mathcal{O}(1)) 的，开始时计算一次需要 (mathcal{O}(Nlog N))，这就是总复杂度。

注意事项

根据下标起始的不同，每一次转所标记的公式也不同，所以不要乱抄代码；
注意有意义的变量名，否则这道题会十分混乱。

Code

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

typedef long long ll;
const int max_n = 100000;

struct ut // 排序用
{
	int id, val, ord;
};

int a[max_n], b[max_n], tr[max_n+1], n;
ut v[max_n];

inline int lowbit(int x) { return x & -x; }
inline bool cmpv(const ut& a, const ut& b) { return a.val < b.val; } // 两次排序关键字不同
inline bool cmpo(const ut& a, const ut& b) { return a.ord < b.ord; }

#define gc getchar // 快读
inline int read()
{
	int c = gc(), t = 1, n = 0;
	while (isspace(c)) { c = gc(); }
	if (c == '-') { t = -1, c = gc(); }
	while (isdigit(c)) { n = n * 10 + c - '0', c = gc(); }
	return n * t;
}
#undef gc

void add(int id) // 树状数组的修改
{
	while (id <= n)
	{
		tr[id]++;
		id += lowbit(id);
	}
}

int get(int id) // 询问
{
	int ret = 0;

	while (id > 0)
	{
		ret += tr[id];
		id -= lowbit(id);
	}

	return ret;
}

int main()
{
	ll ans, cnt = 0, pref = 0;

	n = read();
	for (int i = 0; i < n; i++) // 输入
		a[i] = read() - 1, v[a[i]].val = i;
	for (int i = 0; i < n; i++)
		b[i] = read() - 1, v[b[i]].id = i, v[i].ord = i;
	
	sort(v, v + n, cmpv);

	for (int i = n; i > 0; i--) // 排序后求逆序对
	{
		cnt += get(v[i-1].id + 1);
		add(v[i-1].id + 1);
	}

	sort(v, v + n, cmpo); // 重新排一次

	ans = cnt;
	for (int i = 0; i < n; i++) // 滚 b
	{
		pref += n - 2 * v[b[i]].val - 1;

		if (cnt + pref < ans)
			ans = cnt + pref;
	}
	
	pref = 0;
	for (int i = 0; i < n; i++) // 再滚 a
	{
		pref += n - 2 * v[a[i]].id - 1;

		if (cnt + pref < ans)
			ans = cnt + pref;
	}

	printf("%lld
", ans); // 两次统计最终答案

	return 0; // 然后就 AC 了、
}