NC14661 简单的数据结构 双端队列deque

链接：https://ac.nowcoder.com/acm/problem/14661
来源：牛客网

题目描述
栗酱有一天在网上冲浪的时候发现了一道很有意思的数据结构题。
该数据结构形如长条形。

一开始该容器为空，有以下七种操作。

1 a从前面插入元素a

2 从前面删除一个元素

3 a从后面插入一个元素

4 从后面删除一个元素

5 将整个容器头尾翻转

6 输出个数和所有元素

7 对所有元素进行从小到大排序
输入描述:

只有一组数据，第一行n≤50000,m≤200000, a≤100000 代表最大数据数目和操作次数。
接下来每一行一个操作如上描述。保证所有操作合法（不会在容器为空时删除元素）。
6、7操作共计不会超过10次。

输出描述:

当执行6操作时，第一行先输出当前的个数，然后从头到尾按顺序输出，每两个元素之间用一个空格隔开，末尾不能有空格。

示例1
输入
复制

10 9
1 1
3 5
3 4
6
4
5
6
7
6

输出
复制

3
1 5 4
2
5 1
2
1 5

比较简单的队列模拟题,如果翻转和排序操作出现概率和其他5种一样的话我就不会写了,

• 翻转并不用真的去翻转,可以添加一个翻转标记 $rev$rev,偶数次翻转相当于没翻转
• 当 $rev$rev为真时,插头变成插尾,删头变成删尾,逆序排序
• 当 $rev$rev为假时,正常插头插尾,正常删头删尾,正序排序

#define debug
#ifdef debug
#include <time.h>
#include "/home/majiao/mb.h"
#endif

#include <iostream>
#include <algorithm>
#include <vector>
#include <string.h>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <math.h>

#define MAXN ((int)1e5+7)
#define ll long long int
#define INF (0x7f7f7f7f)
#define fori(lef, rig) for(int i=lef; i<=rig; i++)
#define forj(lef, rig) for(int j=lef; j<=rig; j++)
#define fork(lef, rig) for(int k=lef; k<=rig; k++)
#define QAQ (0)

using namespace std;

#ifdef debug
#define show(x...) \ do { \ cout << "\033[31;1m " << #x << " -> "; \ err(x); \ } while (0)

void err() { cout << "\033[39;0m" << endl; }
template<typename T, typename... A>
void err(T a, A... x) { cout << a << ' '; err(x...); }
#endif

#ifndef debug
namespace FIO {
	template <typename T>
	void read(T& x) {
		int f = 1; x = 0;
		char ch = getchar();

		while (ch < '0' || ch > '9') 
			{ if (ch == '-') f = -1; ch = getchar(); }
		while (ch >= '0' && ch <= '9') 
			{ x = x * 10 + ch - '0'; ch = getchar(); }
		x *= f;
	}
};
using namespace FIO;
#endif


int n, m, Q, K, rev, lef=MAXN, rig=MAXN-1, que[MAXN<<2];
#define PUSH_BACK(x) (que[++rig] = x)
#define PUSH_FRONT(x) (que[--lef] = x)
#define POP_BACK (rig = lef < rig ? --rig : rig)
#define POP_FRONT (lef = lef < rig ? ++lef : lef)

void push_front(int x) {
	if(rev) //已经翻转
		PUSH_BACK(x);
	else 
		PUSH_FRONT(x);
}

void push_back(int x) {
	if(rev) //已经翻转
		PUSH_FRONT(x);
	else
		PUSH_BACK(x);
}

void pop_front() {
	if(rev) //已经翻转
		POP_BACK;
	else
		POP_FRONT;
}

void pop_back() {
	if(rev) //已经翻转
		POP_FRONT;
	else
		POP_BACK;
}

void output() {
// forarr(que, lef, rig);
	printf("%d\n", rig-lef+1);
	if(rev) {
		for(int i=rig; i>=lef; i--) 
			printf("%d%c", que[i], i==lef?'\n':' ');
	} else {
		for(int i=lef; i<=rig; i++) 
			printf("%d%c", que[i], i==rig?'\n':' ');
	}
}

void trysort() {
	if(lef > rig) return ;
	if(rev) {
		//翻转的话要逆序排序
		sort(que+lef, que+lef+(rig-lef+1), greater<int>());
	} else {
		sort(que+lef, que+lef+(rig-lef+1));
	}
}

int main() {
#ifdef debug
	freopen("test", "r", stdin);
	clock_t stime = clock();
#endif
	read(n), read(Q);
	int op, x;
	while(Q--) {
		read(op);
		if(op == 1) {
			read(x);
			push_front(x);
		} else if(op == 2) {
			pop_front();
		} else if(op == 3) {
			read(x);
			push_back(x);
		} else if(op == 4) {
			pop_back();
		} else if(op == 5) {
			rev = !rev;
		} else if(op == 6) {
			output();
		} else if(op == 7) {
			trysort();
		}  
	}





#ifdef debug
	clock_t etime = clock();
	printf("rum time: %lf 秒\n",(double) (etime-stime)/CLOCKS_PER_SEC);
#endif 
	return 0;
}