『贪心·二分答案』排序

P r o b l e m \mathrm{Problem} Problem

---

S o l u t i o n \mathrm{Solution} Solution

这道题有一个很神奇的性质：交换操作与操作顺序无关。

这意味着，我们形如 a b a b a b . . . ababab... ababab... 的操作顺序可以改变成形如 a a a b b b . . . aaabbb... aaabbb... 的顺序。

考虑证明：若有交换操作 ( a , b ) (a,b) (a,b) 和 ( c , d )   ( a < b , c < d ) (c,d)\ (a<b,c<d) (c,d) (a<b,c<d).

• 自己和自己交换显然满足上述结论，故不作考虑。
• 若 a , b , c , d a,b,c,d a,b,c,d 四个数不相同，则两个操作可以交换。
• 若 a = c , b = d a=c,b=d a=c,b=d，则两个交换本生便没有意义，故可以交换。
• 若 a = d a=d a=d或 b = c b=c b=c，则两次操作形如 ( a , b ) (a,b) (a,b)和 ( b , c ) (b,c) (b,c)，则该操作可以用 ( b , c ) (b,c) (b,c) 和 ( a , c ) (a,c) (a,c) 代替;若形式为 ( b , c ) (b,c) (b,c) 和 ( a , b ) (a,b) (a,b) ，则可以使用 ( a , b ) (a,b) (a,b) 和 ( a , c ) (a,c) (a,c) ，那么只要其中的某一个是Alice的操作，则Alice和Bob的操作顺序一定可以通过Bob的改变而交换。
• 当 a = c a=c a=c或 b = d b=d b=d，则证明方法与上面同理。

操考试就应该大胆猜想的

上述结论说明了： a b ab ab 操作和 b a ba ba 是等下的，那么若干次等价交换我们就可以得到上述交换顺序的改变。显然答案具有单调性，我们尝试枚举Alice的熟悉 x x x。

• 我们交换完Alice的前 x x x 的操作以后，我们我们只判定改变当前数列的次数是否 ≤ x \le x ≤x 即可。因此少了，我们可以用自我交换完成填充。

---

C o d e \mathrm{Code} Code

#include <bits/stdc++.h>

using namespace std;
const int N = 7e5;

int n, m;
int a[N], vis[N], b[N], x[N], y[N];

int read(void)
{
	int s = 0, w = 0; char c = getchar();
	while (!isdigit(c)) w |= c == '-', c = getchar();
	while (isdigit(c)) s = s*10+c-48, c = getchar();
	return w ? -s : s;
}

void Dfs(int x)
{
	vis[x] = 1;
	if (vis[b[x]] == 0) Dfs(b[x]);
}

bool check(int t)
{
	int res = n;
	for (int i=1;i<=n;++i) {
		b[i] = a[i];
		vis[i] = 0;
	}
	for (int i=1;i<=t;++i) swap(b[x[i]], b[y[i]]);
	for (int i=1;i<=n;++i)
		if (vis[i] == 0) Dfs(i), res --;
	return res <= t;
}

int main(void)
{
	freopen("sort.in","r",stdin);
	freopen("sort.out","w",stdout);
	n = read();
	for (int i=1;i<=n;++i) a[i] = read() + 1;
	m = read();
	for (int i=1;i<=m;++i) {
		x[i] = read() + 1;
		y[i] = read() + 1;
	} 
	int l = 0, r = m;
	while (l + 1 < r) {
		int mid = l + r >> 1;
		if (check(mid)) r = mid;
		else l = mid;
	}
	if (check(l)) cout << l << endl;
	else cout << r << endl;
	return 0;
}