---

第一行一个整数表示$n$。
第二行$n$个整数表示初始序列。（这行原题没有，是我加的）
接下来$2n$行每行两个整数，分别表示$X_i,Y_i$。
数据保证至少存在一种方案使得游戏在$2n$轮之内完成。

---

一个整数表示小$A$最少需要进行的轮数。

---

样例输入：

3
1 0 2
1 2
0 2
0 0
0 1
0 2
1 2

样例输出：

2

---

样例解释：

最优方案为第一轮中交换下标为$0$和$1$的元素，第二轮交换下标为$0$和$0$的元素，也就是不改变这个排列。

数据范围：

对于前$20\%$的数据：
$n\leqslant 10$
对于前$40\%$的数据：
$n\leqslant 2,000$
对于所有数据：
$1\leqslant n\leqslant 200,000$

---

首先，来看着道题的两条特殊性质：

　　$\alpha.$如果在小$B$换之前这个序列就已经排好序了，那么小$A$可以把它再换回来。

　　$\beta.$如果答案为$k$，那么小$A$可以让小$B$先都换完了再都换回来，举个例子，比方说$1,2,3$三个数，小$A$要交换$1,3$，现在小$B$交换了$1,2$，那么我们无非就是将需要交换的位置改变，内容并不需要改变。

这样，答案就满足单调性了，我们考虑二分答案，至于$judge$，上面已经提到了一部分，下面主要讲一下小$A$应该如何换，我们只需要从左往右扫，如果现在位置上的数不是应该有的数，我们换过来就好了。

下面代码中给出了两种不同的$judge$方式。

其实我们在$n$步之内一定能换过来，所以下面的代码只读了前$n$步。

时间复杂度：$\Theta(n\log n)$。

期望得分：$100$分。

实际得分：$100$分。

---

#include
using namespace std;
int n;
int a[200001],b[200001],pos[200001];
int l[500000],r[500000];
bool judge(int x)
{
for(int i=1;i<=n;i++)b[i]=a[i]; for(int i=1;i<=x;i++)swap(b[l[i]],b[r[i]]); for(int i=1;i<=n;i++)pos[b[i]]=i; int res=0; for(int i=1;i<=n;i++) if(b[i]!=i) { res++; pos[b[i]]=pos[i]; swap(b[pos[i]],b[i]); } if(res<=x)return 1; return 0; } bool judge(int x) { for(int i=1;i<=n;i++)b[i]=a[i]; for(int i=1;i<=x;i++)swap(b[l[i]],b[r[i]]); int res=0; for(int i=1;i<=n;i++) while(b[i]!=i) { res++; swap(b[i],b[b[i]]); } if(res<=x)return 1; return 0; } int main() { scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); a[i]++; } for(int i=1;i<=n;i++) { scanf("%d%d",&l[i],&r[i]); l[i]++;r[i]++; } int lft=0,rht=n; while(lft>1;
if(judge(mid))rht=mid;
else lft=mid+1;
}
printf("%d",lft);
return 0;
}

---

rp++