题解：CF1981C（Turtle and an Incomplete Sequence）

Part 1：题意理解

• 地址链接：CF、洛谷。
• 题面翻译：给定一个长度为 $n$ 的序列 $a$，其中有一些元素未知，用 $-1$ 表示，现在要将数组 $a$ 补充完整，即将 $a$ 中所有的 $-1$ 替换成一个小于等于 $10^9$ 的正整数，使得对于任意一个 $1\le i<n$，都有 $a_i=\lfloor \frac{a_{i+1}}{2}\rfloor$ 或者 $a_{i+1}=\lfloor \frac{a_i}{2}\rfloor$。如果存在合法的方案，输出填充后的数组，否则输出 $-1$。
• 数据范围：$n\le 2\cdot 10^5$，只能接受线性算法。

Part 2：算法分析

• 典型构造题。
• 首先特判，如果 $a$ 中所有元素都未知，那么就 $1$ 和 $2$ 交替输出。
• 由于前缀和后缀的 $-1$ 都很好处理，并且对中间没有影响，先将他们特别处理。具体的，以前缀为例，假设 $a_1$ 到 $a_i$ 均为 $-1$，且 $a_{i+1}$ 不是 $-1$，是已知的，那么将 $1$ 到 $i$ 中所有与 $i+1$ 奇偶性相同的赋值为 $a_{i+1}$，其余赋值为 $a_{i+1}\times 2$。
• 对于中间，每个连续的 $-1$ 组成的段是独立的，可分别处理。假设现在处理的是 $a_u$ 到 $a_v$ 这个段，我们的目标就是通过 $v-u+2$ 次乘 $2$、除以 $2$ 的操作让 $a_{u-1}$ 变成 $a_{v+1}$。也就是说 $a_{u-1}\ne -1$，$a_u$ 到 $a_v$ 都是 $-1$，$a_{v+1}\ne -1$。根据题面分析，其实说 $a_i$ 和 $a_{i+1}$ 满足条件，实际上就是说它们在由 $1$ 到 $n$ 编号的节点组成的完全二叉树上是相邻的。因此，$a_{u-1}$ 通过一些操作变成 $a_{v+1}$，就相当于在这棵完全二叉树上找到一个从 $a_{u-1}$ 走到 $a_{v+1}$ 的长度等于 $v-u+2$ 的路径。
• 如何找这条路径呢？显然，只要找出两个节点的 LCA，按照 $a_{u-1}$ 到 LCA 再到 $a_{v+1}$ 的顺序走就能得出最短的一条路径。至于怎么使它加长，就可以直接在某个点上，比如 LCA，不断地乘 $2$、除以 $2$ 就可以了。当然，如果奇偶性不对，或者最短的长度也不够，自然不行。
• 但是如何实现呢？有两个指针分别指向这段未知的元素内最左侧、最右侧仍旧没有填充的位置。每一次，如果某一侧最后一个已经填充完成的数较大，就让对应侧的指针对应的元素赋值为它除以 $2$。如果两侧相等，就让其中一个能除以二就除以二；不能除以二，也就是说对应的已经处理完的是 $1$，就乘二。最后判断两个方向最后一个赋值的是否满足条件即可。

Part 3：代码实现

#include <bits/stdc++.h>
#define N 220000
using namespace std;
int t, n, a[N];
int s, lst, u, v;
bool flag;
int main() {
	scanf("%d", &t);
	while (t--) {
		scanf("%d", &n);
		s = 0;
		for (int i = 1; i <= n; i++) {
			scanf("%d", &a[i]);
			if (a[i] == -1) {
				s++;
			}
		}
		flag = false;
		for (int i = 2; i <= n; i++) {
			if (a[i - 1] != -1 && a[i] != -1 && a[i - 1] != a[i] / 2 && a[i] != a[i - 1] / 2) {
				flag = true;
				break;
			}
		}
		if (flag == true) {
			printf("-1\n");
			continue;
		}
		if (s == n) {
			for (int i = 1; i <= n; i++) {
				if (i % 2 == 0) {
					printf("1 ");
				} else {
					printf("2 ");
				}
			}
			printf("\n");
		} else {
			lst = -1;
			for (int i = 1; i <= n; i++) {
				if (a[i] != -1) {
					lst = i;
					break;
				}
			}
			for (int i = lst - 1; i >= 1; i--) {
				if (i % 2 == lst % 2) {
					a[i] = a[lst];
				} else {
					a[i] = a[lst] * 2;
				}
			}
			lst = -1;
			for (int i = n; i >= 1; i--) {
				if (a[i] != -1) {
					lst = i;
					break;
				}
			}
			for (int i = lst + 1; i <= n; i++) {
				if (i % 2 == lst % 2) {
					a[i] = a[lst];
				} else {
					a[i] = a[lst] * 2;
				}
			}
			lst = -1;
			flag = true;
			for (int i = 1; i <= n; i++) {
				if (a[i] == -1) {
					if (lst == -1) {
						lst = i;
					}
					if (a[i + 1] != -1) {
						u = lst;
						v = i;
						while (u <= v) {
							if (a[u - 1] > a[v + 1]) {
								a[u] = a[u - 1] / 2;
								u++;
							} else if (a[u - 1] < a[v + 1] ){
								a[v] = a[v + 1] / 2;
								v--;
							} else {
								if (a[u - 1] == 1) {
									a[u] = a[u - 1] * 2;
								} else {
									a[u] = a[u - 1] / 2;
								}
								u++;
							}
						}
						if (a[u] != a[v] / 2 && a[v] != a[u] / 2) {
							flag = false;
							break;
						}
						lst = -1;
					}
				}
			}
			if (flag == false) {
				printf("-1\n");
			} else {
				for (int i = 1; i <= n; i++) {
					printf("%d ", a[i]);
				}
				printf("\n");
			}
		}
	}
	return 0;
}