NOIP2013提高组火柴排队

P1966

题目大意：
有两个序列A, B, 长度为n
定义分值为 $\sum\limits^{n}_{i=1} (A_i - B_i)^2$
求让 A, B 达到最大分值的最小交换次数

不满足单调性不能二分，怎么办？
研究题目性质!

我们看这个 $(A_i - B_i) ^ 2$ , 拆成这样 $A_i^2+B_i^2-2A_iB_i$ ,这里所有的 $A_i^2$ 和 $B_i^2$ 都是无法改变的，只能考虑改变 $A_iB_i$ 的值，学过贪心的我们肯定都知道, 有序优于无序。
我们令 $Q_{A_i} = B_i$ , 然后求一下逆序对的数目就好啦~

实践上

1. 数值很大要注意离散化
2. 题目要求取模哦 (否则会 80 分)
3. 逆序对可以用树状数组或归并做，暴力会 TLE

下面给出代码

#include <bits/stdc++.h>
#define int long long // 不用 long long 也可以过
using namespace std;

const int N = 1e5 + 10;
const int P = 1e8 - 3;

int a[N], b[N], c[N], d[N], n, e[N], cnt;
int p[N];


// 这是逆序对模板
void merge_sort(int *A, int x, int y, int *T, int &cnt)
{
	if (y - x > 1)
	{
		int m = x + (y - x) / 2;
		int p = x, q = m, i = x;
		merge_sort(A, x, m, T, cnt);
		merge_sort(A, m, y, T, cnt);
		while (p < m || q < y)
		{
			if (q >= y || (p < m && A[p] <= A[q]))
				T[i++] = A[p++];
			else
			{
				T[i++] = A[q++];
				cnt += m - p;
                cnt %= P; // 别忘记取模
			}
		}
		for (int i = x; i < y; i++)
			A[i] = T[i];
	}
}

signed main(void)
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i], c[i] = i;
    for (int i = 1; i <= n; i++)
        cin >> b[i], d[i] = i;

    sort(c + 1, c + n + 1, [&](const int &i, const int &j) -> bool
         { return a[i] < a[j]; });

    sort(d + 1, d + n + 1, [&](const int &i, const int &j) -> bool
         { return b[i] < b[j]; });

    for(int i = 1; i <= n; i++) e[c[i]] = d[i];

    cnt = 0;
    merge_sort(e, 1, n + 1, p, cnt);
    cout << cnt % P; // 别忘记取模（其实这里不取模也没关系，因为上面取模了
}