Problem Link

朴素思路就是用所有开关建一棵叶子个数为 $2^t$ 的满二叉树，其中 $2^t>n$，所有叶子按遍历顺序填 $a_1\sim a_n,0$，长度 $<2^t$ 的部分用 $-1$ 在开头补齐。

但此时大小可以达到 $2n$ 级别，考虑有什么办法能优化点数。

首先满二叉树的结构不能动，否则无法保证每个开关被还原，我们只能在树的基础上缩减节点。

考虑一个所有叶子权值相同的子树，可以直接把这个权值写到根上。

自然想到把所有 $-1$ 不按遍历顺序，而是直接放到树的最左侧，此时代价就不超过 $n+\log_2n$，只要我们保证在访问最后一个叶子之前经过了这些 $-1$ 即可，显然最后一个叶子在最右侧，所以这些 $-1$ 肯定会被经过。

实现的时候可以发现叶子的遍历顺序就是位逆序，直接处理即可。

时间复杂度 $\mathcal O(n)$。

代码：

#include<bits/stdc++.h>
using namespace std;
void answer(vector<int>C,vector<int>X,vector<int>Y);
const int MAXN=5e5+5;
int p[MAXN],l[MAXN],r[MAXN],q;
int sol(const vector<int>&a) {
	if(count(a.begin(),a.end(),a[0])==(int)a.size()) return a[0];
	int u=++q; vector <int> L,R;
	for(int i=0;i<(int)a.size();++i) (i&1?R:L).push_back(a[i]);
	l[u]=sol(L),r[u]=sol(R);
	return -u;
}
void create_circuit(int m,vector<int>a)  {
	a.push_back(0);
	int n=a.size(),d=1;
	while(d<n) d<<=1;
	for(int i=1;i<d;++i) p[i]=(p[i>>1]>>1)|((i&1)*(d/2));
	vector <int> b(d);
	for(int i=0;i<d-n;++i) b[p[i]]=-1;
	for(int i=0,j=0;i<n;++i) {
		while(b[j]) ++j;
		b[j]=a[i];
	}
	int o=sol(b);
	answer(vector<int>(m+1,o),vector<int>(l+1,l+q+1),vector<int>(r+1,r+q+1));
}