牛客小白月赛29 F-项链

项链

分析

• 让我们暂且不看区间反转操作，只先考虑移动点的问题。毫无疑问，可以用链表实现。

  设 ,其中 表示位置在编号为i的珠子之后的珠子编号，注意，是编号， 则表示位置在编号为i的珠子之前的珠子编号。

  假设就是下面的图
  
  如果我们要移动其中一个点，得先删点
  
  然后重新加入
  

  然后考虑翻转操作，因为一旦翻转了，前变后，后变前，那之前编号为i的点的下一个位置的f[1][i]此时就会在他的前面，成为所谓的f[0][i]，假设此时要输出，怎么办？倒序啊！这不就是解决的办法吗。如果此时要修改，怎么办？比如说，此时我要把编号为 x 的换到 y 的后面，但我的原序列并没有翻转，
  
  如果我要把4换到2的后面，此时我只需要在未翻转的序列中把4换到2的前面即可，仅需要倒序输出也可以得到正确答案

  代码

#include<bits/stdc++.h>

using namespace std;

const int N=1e4+10;

int n,m;
int f[2][N],b[N];

inline void print()
{
    int st=0;
    for (int i=0;i<n;i++)
        if(b[i]==1)
        {
            st=i;
            break;
        }

    for (int i=0;i<n;i++)
    {
        printf("%d",b[(st+i)%n]);
        if(i==n-1) puts("");
        else printf(" ");
    }
}

int main()
{
    scanf("%d%d",&n,&m);
    f[1][0]=1;f[0][n+1]=n;
    for (int i=1;i<=n;i++)
        f[0][i]=i-1,f[1][i]=i+1;
    //0:上一个,1:下一个
    int d=0;
    for (int i=1,op;i<=m;i++)
    {
        scanf("%d",&op);
        if(op==1)
        {
            int x,y;scanf("%d%d",&x,&y);
            f[d^1][f[d][x]]=f[d^1][x];
            f[d][f[d^1][x]]=f[d][x];//删除 

            f[d][x]=y;
            f[d^1][x]=f[d^1][y];//加点 

            f[d][f[d^1][y]]=x;
            f[d^1][y]=x;//更新
        }
        else if(op==2)
        {
            int x,y;scanf("%d%d",&x,&y);
            f[d^1][f[d][x]]=f[d^1][x];
            f[d][f[d^1][x]]=f[d][x];

            f[d^1][x]=y;
            f[d][x]=f[d][y];
            f[d^1][f[d][y]]=x;
            f[d][y]=x;
        }
        else if(op==3) d^=1;
        else
        {
            if(d==0)
            {
                int st=f[1][0];
                for (int j=1;j<=n;j++)
                {
                    b[j-1]=st;
                    st=f[1][st];
                }print();
            }
            else
            {
                int st=f[0][n+1];
                for (int j=1;j<=n;j++)
                {
                    b[j-1]=st;
                    st=f[0][st];
                }print();
            }
        }
    }

    return 0;
}