P6823 「EZEC-4」zrmpaul Loves Array

发现进行一次排序后先前的操作都无效了，所以只需做最后一次排序后的操作。翻转操作打个翻转标记，互换操作根据翻转标记即可。

时间复杂度 \(O\left(n+m\right)\)。

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;

}

巴特西

P6823 「EZEC-4」zrmpaul Loves Array

最新文章

热门文章