CF 675E

• 题目很好，傻逼的WA了两发。
  @题意：第$i$个点只能与$[i+1,ai]$这些点有向边直接相连，然后对所有的$P{_i}{_j}$计数求和，$P{_i}{_j}$表示表示$i$到$j$的最短路$(i<j)$，$n < 10^5$。

  @思路：$dp[i]$表示$i$到后面的点的最短路计数，注意到每个点所直接相连的点都是连续的一段区间，我以这段区间内的某个数为跳板，可以连接后面的点。这里有个显然的贪心策略就是，选触手最远的那个点，至于证明，可以考虑每个点所连的点都是连续的一段区间，假设选择触手第二远的点，以此为中转点到达下标更大的点$j$，那么一定可以选择触手最远的那个点，也能到达点$j$，反过来触手最远的点能到达的第二远的不一定直接可达。我们就有了初步的一个转移方程$dp[i]=dp[j] + n-i$, $j$ 为触手最远的那个点。
  意义就是由触手最远的那个点转移过来，然后新的点$i$对答案的新的贡献就是在$i$这个点之后的点数之和，因为你可以在$j$的基础上都已到达任意点或者以$j$点为中转点到达任意点。但是还有一个bug，就是比如$6$的直接可达区间是$[7, 8]$，假设$7$是触手最远的点，那么,$dp[7] + n - i$ 那么就相当于$6$通过$7$到达了$8$，然后又算了一遍$6$直接到$8$。所以要消除这个重复，观察到$6$能到达的点可以直接连边，其他点通过$7$来中转，很巧的是$6$能直接到的点$7$都能直接到达(因为$7$是触手最远的啊)，所以就是重复了$8-7$个点。更一般的，就是重复了$r-j$个点，$r$是$i$点在一步内能到达的最远的点。最终确定状态转移方程：$dp[i] = dp[j] + (n-i) - (r-j)$

#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
const int maxn = 100007;
int n, right[maxn];
long long dp[maxn];
struct SegTree{ int l, r, val, id; } seg[maxn * 4];
void build(int l, int r, int k)
{
    seg[k].l = l;
    seg[k].r = r;
    if(l == r){
        seg[k].id = l;
        seg[k].val = right[l];
        return;
    }
    int mid = (l + r) / 2;
    build(l, mid, 2 * k);
    build(mid + 1, r, 2 * k + 1);
    if(seg[2 * k].val > seg[2 * k + 1].val){
        seg[k].id = seg[2 * k].id;
        seg[k].val = seg[2 * k].val;
    } else {
        seg[k].id = seg[2 * k  + 1].id;
        seg[k].val = seg[2 * k + 1].val;
    }
}
int ans, id;
void ask(int l, int r, int k){
    if(l <= seg[k].l && seg[k].r <= r){
        if(ans <= seg[k].val){
            id  = seg[k].id;
            ans = seg[k].val;
        }
        return;
    }
    int mid = (seg[k].l + seg[k].r) / 2;
    if(r <= mid) ask(l, r, 2 * k);
    else if(l > mid) ask(l, r, 2 * k + 1);
    else ask(l, mid, 2 * k), ask(mid + 1, r, 2 * k + 1);
}
int main()
{
    std::cin >> n;
    right[n] = n;
    for(int i = 1; i < n; i ++){
        std::cin >> right[i];
    }
    build(1, n, 1);
    long long temp = 0;
    for(int i = n - 1; i > 0; i --){
        int l = i + 1, r = right[i];
        ans = 0;
        ask(l, r, 1);
        if(ans <= r) id = r;
        dp[i] = (n - i) + dp[id] - (r - id);
        temp += dp[i];
    }
    std::cout << temp << "\n";
}