codeforces 675E E. Trains and Statistic(线段树+dp)

题目链接：

E. Trains and Statistic

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

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 ai 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.

Input

The first line of the input contains a single integer n (2 ≤ n ≤ 100 000) — the number of stations.

The second line contains n - 1 integer ai (i + 1 ≤ ai ≤ n), the i-th of them means that at the i-th station one may buy tickets to each station from i + 1 to ai inclusive.

Output

Print the sum of ρi, j among all pairs of 1 ≤ i < j ≤ n.

Examples

input

4
4 4 4

output

input

5
2 3 5 5

output

17

题意：

a[i]表示从第i个车站可以一张票到第[i+1,a[i]]这些车站;
p[i][j]表示从第i个车站到第j个车站的最少的票数,现在要求∑dp[i][j](1<=i<=n,i<j<=n);

思路：

dp[i]=∑p[i][j](i<j<=n);
转移方程为dp[i]=dp[temp]+(n-i)-(a[i]-temp);
其中temp表示[i+1，a[i]]中a[temp]最大的位置;

AC代码：

#include <bits/stdc++.h>

using namespace std;

#define Riep(n) for(int i=1;i<=n;i++)

#define Riop(n) for(int i=0;i<n;i++)

#define Rjep(n) for(int j=1;j<=n;j++)

#define Rjop(n) for(int j=0;j<n;j++)

#define mst(ss,b) memset(ss,b,sizeof(ss));

typedef long long LL;

const LL mod=1e9+;

const double PI=acos(-1.0);

const int inf=0x3f3f3f3f;

const int N=1e5+;

int n,a[N];

LL dp[N];

struct Tree

{

    int l,r,ans;

}tr[*N];

void pushup(int o)

{

    if(a[tr[*o].ans]>a[tr[*o+].ans])tr[o].ans=tr[*o].ans;

    else tr[o].ans=tr[*o+].ans;

}

void build(int o,int L,int R)

{

    tr[o].l=L;

    tr[o].r=R;

    if(L==R)

    {

        tr[o].ans=L;

        return ;

    }

    int mid=(L+R)>>;

    build(*o,L,mid);

    build(*o+,mid+,R);

    pushup(o);

}

int query(int o,int L,int R)

{

    if(L<=tr[o].l&&R>=tr[o].r)return tr[o].ans;

    int mid=(tr[o].l+tr[o].r)>>;

    if(R<=mid)return query(*o,L,R);

    else if(L>mid)return query(*o+,L,R);

    else

    {

        int fl=query(*o,L,mid),fr=query(*o+,mid+,R);

        if(a[fl]>a[fr])return fl;

        else return fr;

    }

}

int main()

{

    scanf("%d",&n);

    Riep(n-)scanf("%d",&a[i]);

    a[n]=n-;

    build(,,n);

    LL ans=;

    dp[n]=;

    for(int i=n-;i>;i--)

    {

        int temp=query(,i+,a[i]);

        dp[i]=dp[temp]+(LL)(n-i-(a[i]-temp));

        ans+=dp[i];

    }

    cout<<ans<<"\n";

    return ;

}

巴特西

codeforces 675E E. Trains and Statistic(线段树+dp)

最新文章

热门文章