题目解析：Wyliczanka（儿歌选玩具）

问题理解

Bajtosia 有一个长度为 n 的玩具序列，她通过念儿歌在这些玩具间移动来选择玩具。给定每个玩具被指向的次数序列 a₁, a₂, ..., aₙ，我们需要判断是否存在一条合法的移动路径（从某个玩具开始，每次移动到相邻玩具，在某个玩具结束）使得每个玩具被指向的次数恰好等于给定的 aᵢ。

关键观察

1. 非零区间必须连续

如果存在有效的移动路径，那么所有被访问过的玩具（aᵢ > 0）必须构成一个连续区间。如果中间有零值，则路径无法跳过这些位置。

2. 单点情况

如果只有一个玩具被访问（即只有一个 aᵢ > 0），那么该值必须为 1，因为路径至少包含一个点。

3. 访问次数的约束关系

对于连续的非零区间，相邻玩具的访问次数需要满足特定的约束条件。代码中使用了一个巧妙的递推方法来验证这些约束。

算法思路

步骤 1：确定非零区间

• 找到第一个非零位置 l 和最后一个非零位置 r
• 检查区间 [l, r] 内是否包含零值，如果包含则直接返回 "NIE"

步骤 2：处理单点情况

• 如果 l = r（只有一个非零点），检查 a[l] 是否为 1

步骤 3：递推验证约束

这是算法的核心部分，通过维护两个变量来验证约束：

1. s[i]：表示处理到位置 i 时的状态值
2. cnt：计数器，表示需要额外调整的次数

递推过程：

• 初始化：s[l] = a[l] * 2
• 对于 i 从 l+1 到 r：
  • 计算 s[i] = (a[i] + cnt) * 2 - s[i-1]
  • 如果 s[i] < 2，需要调整 cnt 使 s[i] ≥ 2
  • 检查约束条件：如果 cnt = 2 且 s[i] > cnt，则无效

步骤 4：最终检查

• cnt ≤ 2
• s[r] = 2

算法正确性分析

这个算法基于以下观察：

1. 有效的移动路径必须满足特定的奇偶性和边界条件
2. cnt 实际上记录了路径的"转折点"数量，有效的路径最多有 2 个主要转折点
3. s[r] = 2 确保了路径的正确结束

时间复杂度

• 每个测试用例 O(n)
• 总复杂度 O(∑n) ≤ O(10⁶)，满足题目要求

样例验证

以第一个样例 [1, 3, 1] 为例：

• l = 1, r = 3
• 区间内无零值
• 递推过程：
  • s[1] = 2
  • s[2] = (3+0)×2 - 2 = 4
  • s[3] = (1+0)×2 - 4 = -2 → 调整后 s[3] = 2, cnt = 2
• 最终检查：cnt = 2 ≤ 2, s[3] = 2，输出 "TAK"

这个算法巧妙地通过递推关系验证了移动路径的合法性，避免了复杂的图论或动态规划方法。