📝 题目大意

给定长度为 $n$ 的序列 $a$，初始空序列 $b$。依次对 $i=1,2,\ldots,n$ 执行：将 $a_i$ 追加到 $b$ 末尾，再将 $b$ 反转。求最终序列 $b$。

💡 解题思路

1. 题目分析：若直接模拟，每次反转 $O(|b|)$，总复杂度 $O(n^2)$，在 $n \leq 2\times 10^5$ 下不可接受。需要寻找规律，避免显式反转。

2. 算法推导：

   • 观察每次操作：先追加到末尾，再整体反转。等价于：将新元素插入到当前序列的另一端，并且"当前方向"发生翻转。
   • 具体来说，第 $i$ 次操作后，序列的"头部"和"尾部"角色互换。因此我们只需维护一个双端队列（deque），根据 $i$ 的奇偶性决定新元素放入哪一端：
     • 当 $i$ 为奇数（$i \& 1$ 为真）：将 $a_i$ 放到当前序列的右端（push_back）。
     • 当 $i$ 为偶数：将 $a_i$ 放到当前序列的左端（push_front）。
   • 为什么这样是对的？以 $n=4$ 为例：
     • 原过程：$[1] \to [2,1] \to [3,1,2] \to [4,2,1,3]$
     • deque 模拟：push_back(1) → [1]；push_front(2) → [2,1]；push_back(3) → [2,1,3]；push_front(4) → [4,2,1,3]。完全一致。
   • 处理完所有 $n$ 个元素后，若 $n$ 为奇数，需要将整个 deque 反转一次（reverse）。原因是：当 $n$ 为奇数时，最后一次操作是 push_back（奇数索引），随后在原过程中会执行一次反转，而我们的 deque 模拟跳过了这次反转，因此需要补上。
   • 最终按顺序输出 deque 中的 $n$ 个元素即可。

3. 边界与细节：

   • $n=1$ 时，push_back(a_1) 后 $n$ 为奇数，执行 reverse，但单元素反转后不变，依然正确。
   • $a_i$ 最大可达 $10^9$，使用 int（32 位有符号）足够存储（C++ int 上限约 $2.1\times 10^9$）。
   • 使用 deque<int> 而非 vector，因为需要两端插入。

⏱️ 复杂度分析

• 时间复杂度：遍历 $n$ 个元素，每次 push_back / push_front 为 $O(1)$，最后 reverse 为 $O(n)$。总复杂度 $O(n)$。
• 空间复杂度：deque 存储 $n$ 个元素，$O(n)$。

💻 标准代码 (C++)

#include<bits/stdc++.h>
using namespace std;
int N,a;
deque<int>q;
int main(){
	cin>>N;
	for(int i=1;i<=N;++i){
		cin>>a;
		// 奇数索引放右端，偶数索引放左端
		if(i&1)q.push_back(a);
		else q.push_front(a);
	}
	// n 为奇数时，最后一次操作是 push_back，需补一次反转
	if(N & 1) reverse(q.begin(), q.end());
	// 按顺序输出最终序列
	for(auto it=q.begin();it!=q.end();++it)cout<<*it<<' ';
	cout<<'\n';
	return 0;
}