n 方排序

ty_mxzhn · 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)。

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