A10426. Trains and Statistic
编程题
普及/提高-
知识点
题目描述
Vasya commutes by train every day. There are $n$ train stations in the city, and at the $i$ -th station it's possible to buy only tickets to stations from $i+1$ to $a_{i}$ inclusive. No tickets are sold at the last station.
Let $ρ_{i,j}$ be the minimum number of tickets one needs to buy in order to get from stations $i$ to station $j$ . As Vasya is fond of different useless statistic he asks you to compute the sum of all values $ρ_{i,j}$ among all pairs $1<=i<j<=n$ .
Let $ρ_{i,j}$ be the minimum number of tickets one needs to buy in order to get from stations $i$ to station $j$ . As Vasya is fond of different useless statistic he asks you to compute the sum of all values $ρ_{i,j}$ among all pairs $1<=i<j<=n$ .
输入格式
The first line of the input contains a single integer $n$ ( $2<=n<=100000$ ) — the number of stations.
The second line contains $n-1$ integer $a_{i}$ ( $i+1<=a_{i}<=n$ ), the $i$ -th of them means that at the $i$ -th station one may buy tickets to each station from $i+1$ to $a_{i}$ inclusive.
The second line contains $n-1$ integer $a_{i}$ ( $i+1<=a_{i}<=n$ ), the $i$ -th of them means that at the $i$ -th station one may buy tickets to each station from $i+1$ to $a_{i}$ inclusive.
输出格式
Print the sum of $ρ_{i,j}$ among all pairs of $1<=i<j<=n$ .
输入输出样例
输入 #1
4 4 4 4
输出 #1
6
输入 #2
5 2 3 5 5
输出 #2
17
说明/提示
In the first sample it's possible to get from any station to any other (with greater index) using only one ticket. The total number of pairs is $6$ , so the answer is also $6$ .
Consider the second sample:
- $ρ_{1,2}=1$
- $ρ_{1,3}=2$
- $ρ_{1,4}=3$
- $ρ_{1,5}=3$
- $ρ_{2,3}=1$
- $ρ_{2,4}=2$
- $ρ_{2,5}=2$
- $ρ_{3,4}=1$
- $ρ_{3,5}=1$
- $ρ_{4,5}=1$
Thus the answer equals $1+2+3+3+1+2+2+1+1+1=17$ .
Consider the second sample:
- $ρ_{1,2}=1$
- $ρ_{1,3}=2$
- $ρ_{1,4}=3$
- $ρ_{1,5}=3$
- $ρ_{2,3}=1$
- $ρ_{2,4}=2$
- $ρ_{2,5}=2$
- $ρ_{3,4}=1$
- $ρ_{3,5}=1$
- $ρ_{4,5}=1$
Thus the answer equals $1+2+3+3+1+2+2+1+1+1=17$ .