发现进行一次排序后先前的操作都无效了,所以只需做最后一次排序后的操作。翻转操作打个翻转标记,互换操作根据翻转标记即可。
时间复杂度 \(O(n+m)\)。
code:
#include<bits/stdc++.h>
using namespace std;
#define N 1000005
#define For(i,x,y)for(i=x;i<=(y);i++)
int x[N],y[N],opt[N],a[N];
int read()
{
int A;
bool K;
char C;
C=A=K=0;
while(C<'0'||C>'9')K|=C=='-',C=getchar();
while(C>'/'&&C<':')A=(A<<3)+(A<<1)+(C^48),C=getchar();
return(K?-A:A);
}
void write(int X)
{
if(X<0)putchar('-'),X=-X;
if(X>9)write(X/10);
putchar(X%10|48);
}
int main()
{
bool rev=0;
int n,m,i,j;
n=read(),m=read();
For(i,1,n)a[i]=i;
For(i,1,m)
{
opt[i]=read();
if(opt[i]==3)x[i]=read(),y[i]=read();
}
i=m;
while(i&&opt[i]>2)i--;
if(opt[i]==2)
For(j,1,n>>1)swap(a[j],a[n-j+1]);
while(++i<=m)
if(opt[i]==3)if(rev)swap(a[n-x[i]+1],a[n-y[i]+1]);
else swap(a[x[i]],a[y[i]]);
else rev^=1;
For(i,1,n)write((rev?a[n-i+1]:a[i])),putchar(' ');
return 0;
}