【牛牛与交换排序】用deque模拟区间反转

牛牛与交换排序
题意是给你一个1-n的排列，问能否存在一个k，使得每次翻转一个长度为k的区间，且每次翻转的区间要比上一次更靠右，问能否找到这样一个k。
手写几组样例便会很清晰地发现，最小的k一定是第一个数字与位置不一样的那个数与自己位置的距离的差值。我们可以令k=abs(pos[i]-i)+1;
接下来就是模拟区间翻转的过程了，我们可以利用stl里面的deque或者写一个平衡树，达到O(n)的复杂度来实现这一过程
这里的deque模拟更多是一种思维的发散，写过类似的题就会写，没写过的话是真的很难想到。具体实现的话，便是在长度为k的队列里，找到翻转后变成位置与数字统一的那个数字，然后把它弹出，插入下一个数，如此反复，用flag来表示弹出的是队首还是队尾
具体实现可以看代码

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define ll long long
#define INF 0x3f3f3f3f
#define rep(i, a, b) for(int i=a;i<=b;i++)
#define per(i, a, b) for(int i=a;i>=b;i--)
using namespace std;
const int maxn=1e5+5;
const ll mod=1e9+7;
inline ll read(){ ll f = 1; ll x = 0;char ch = getchar();while(ch>'9'||ch<'0') {if(ch=='-') f=-1; ch = getchar();}while(ch>='0'&&ch<='9') x = (x<<3) + (x<<1) + ch - '0',  ch = getchar();return x*f; }
inline ll qpow(ll a,ll b,ll MOD=mod){ll res=1;a%=MOD;while(b>0){if(b&1)res=res*a%MOD;a=a*a%MOD;b>>=1;}return res;}

int a[maxn],pos[maxn];

int main()
{
    int n=read(),cur=0,k=1;
    rep(i,1,n) a[i]=read(),pos[a[i]]=i;
    rep(i,1,n)
        if(a[i]!=i)
        {
            cur=i;
            k=abs(pos[i]-i)+1;
            break;
        }
    deque<int>q;
    rep(i,cur,cur+k-1)  q.push_back(a[i]);
    int flag=0;// 0代表插入队首，队尾出队； 1代表队首出队，后面的数插入队尾
    for(int i=cur;i+k-1<=n;i++)
    {
        if(q.front()!=i&&q.back()!=i) { puts("no"); return 0;}  //翻转了也无法按顺序升序
        if(!flag&&q.front()!=i) flag^=1;
        if(flag&&q.back()!=i)   flag^=1;

        if(flag){   //插入队首
            q.pop_back();
            if(i+k<=n) q.push_front(a[i+k]);
        }
        else{       //插入队尾
            q.pop_front();
            if(i+k<=n) q.push_back(a[i+k]);
        }
    }
    rep(i,n-k+2,n)//剩下来的留在队列里的数字一一检验是否已经升序
    {
        int now;
        if(!flag) {
            now = q.front();
            q.pop_front();
        }
        else {
            now = q.back();
            q.pop_back();
        }
        if(now != i) { puts("no"); return 0;}
    }
    puts("yes");
    printf("%d\n",k);
}