## 题目描述

Farmer John has just given the cows a program to play with! The program contains two integer variables, $x$ and $y$, and performs the following operations on a sequence $a_1, a_2, \ldots, a_n$ of positive integers:

- Initially, $x=1$ and $y=0$. If, after any step, $x \le 0$ or $x \gt n$, the program immediately terminates.
- The program increases both $x$ and $y$ by a value equal to $a_x$ simultaneously.
- The program now increases $y$ by $a_x$ while decreasing $x$ by $a_x$.
- The program executes steps 2 and 3 (first step 2, then step 3) repeatedly until it terminates (it may never terminate). So, the sequence of executed steps may start with: step 2, step 3, step 2, step 3, step 2 and so on.

The cows are not very good at arithmetic though, and they want to see how the program works. Please help them!

You are given the sequence $a_2, a_3, \ldots, a_n$. Suppose for each $i \; (1 \le i \le n-1)$ we run the program on the sequence $i, a_2, a_3, \ldots, a_n$. For each such run output the final value of $y$ if the program terminates or $-1$ if it does not terminate.

## 题意概述

有一个包含$n$个数的数列，第$i$项为$a_i$。现有两个数$x=1, \; y=0$。执行以下操作

```
while (!(x <= 0 || x > n)) {
y += a[x], x += a[x];
if (!(x <= 0 || x > n)) y += a[x], x -= a[x];
}
```

给定$a_2, a_3, \ldots, a_n$，对于所有$i \in [1, n-1]$，求对数列$i, a_2, a_3, \ldots, a_n$执行操作后$y$的值。若无限循环则输出$-1$。

数据范围：$2 \le n \le 2 \times 10^5, \; 1 \le a_i \le 10^9$。

## 算法分析

直接模拟肯定会超时。易知从一个位置开始执行操作的顺序是固定的，因此可以用记忆化搜索，记录下每一个位置向左或向右执行操作后的$y$值。如果搜索到一个已搜索过但还没有得到答案的位置，则返回$-1$。

## 代码

#include <iostream> using namespace std; long long n, a[300001], ans[300001][2], to[300001][2], vis[300001][2]; long long dfs(long long t, long long m) { if (ans[t][m]) return ans[t][m]; if (vis[t][m]) return ans[t][m] = -1; vis[t][m] = true; if (to[t][m] < 1 || to[t][m] > n) return ans[t][m] = a[t]; long long ret = dfs(to[t][m], !m); if (ret == -1) ans[t][m] = -1; else ans[t][m] = a[t] + ret; return ans[t][m]; } int main() { cin >> n, vis[1][1] = true; for (int i = 2; i <= n; ++i) cin >> a[i]; for (int i = 2; i <= n; ++i) to[i][0] = i - a[i], to[i][1] = i + a[i]; for (int i = 2; i <= n; ++i) if (!ans[i][0]) dfs(i, 0); for (int i = 1; i < n; ++i) if (ans[i + 1][0] == -1) cout << -1 << endl; else cout << i + ans[i + 1][0] << endl; return 0; }