自动搬运

查看原文

来自洛谷，原作者为

	ty_mxzhn 打破天生的劣等感 || 写作悔恨的未来

搬运于2025-08-24 23:14:41，当前版本为作者最后更新于2025-04-14 12:36:07，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

还没写。

因为只能操作一次，所以不妨找到左右两边最长的不必操作的长度。然后操作中间。

注意到这个长度对于左边就是最长的满足 $a_i=i$ 的前缀。

对于右边就是最长的满足 $a_i=i$ 的后缀。

要特判一开始有序的情况。似乎数据以和为贵了。

注意题面中取模与加的运算顺序。

时间复杂度 $O(nq)$。

wwwwwza 的代码：

#include <bits/stdc++.h>
using namespace std;
const int N=5e3+5;
int n,q,x,y,a[N],ans=0;
int main(){
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	while(q--){
		scanf("%d%d",&x,&y);
		x=(x-1+ans)%n+1;
		y=(y-1+ans)%n+1;
		swap(a[x],a[y]);
		int flag=1;
		for(int i=1;i<=n;i++){
			if(a[i]!=i)flag=0;
		}
		if(flag){
			ans=1;
		}else{
			ans=n;
			for(int i=1;i<=n;i++){
				if(a[i]==i)ans--;
				else break;
			}
			for(int i=n;i>=1;i--){
				if(a[i]==i)ans--;
				else break;
			}
		}
		ans*=ans;
		printf("%d\n",ans);
	}
	return 0;
}

考虑更进一步，用 set 维护两端最长的前缀和后缀，可以做到时间复杂度 $O(q\log n)$。

但是，签到题就没必要了吧。