E. Trains and Statistic
题目连接：
http://www.codeforces.com/contest/675/problem/E
Description
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.
Sample Input
4
4 4 4
Sample Output
6
Hint
题意
你可以从第i个城市买的从i到[i+1,a[i]]的车票，现在Pij表示从i到j的最小车票花费
现在让你求sigma p[i][j]
题解：
考虑 dp[i]表示从i到[i+1,n]的p[i][j]和
那么如果j<=a[i]的话，就+=1，否则就贪心找到[i+1,a[i]]里面a[i]最大的那个车站，转移到这个车站去
dp[i][j] = dp[m][j]+1，这样贪心肯定是最小的
然后根据这个莽一波dp就好了
代码
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+7;
typedef pair<int,int> SgTreeDataType;
struct treenode
{
int L , R ;
SgTreeDataType sum;
void update(int v)
{
sum=make_pair(v,L);
}
};
treenode tree[maxn*4];
inline void push_down(int o)
{
}
inline void push_up(int o)
{
if(tree[2*o].sum.first<=tree[2*o+1].sum.first)
tree[o].sum.second=tree[2*o+1].sum.second;
else
tree[o].sum.second=tree[2*o].sum.second;
tree[o].sum.first = max(tree[2*o].sum.first,tree[2*o+1].sum.first);
}
inline void build_tree(int L , int R , int o)
{
tree[o].L = L , tree[o].R = R,tree[o].sum = make_pair(0,0);
if (R > L)
{
int mid = (L+R) >> 1;
build_tree(L,mid,o*2);
build_tree(mid+1,R,o*2+1);
}
}
inline void update(int QL,int QR,int v,int o)
{
int L = tree[o].L , R = tree[o].R;
if (QL <= L && R <= QR) tree[o].update(v);
else
{
push_down(o);
int mid = (L+R)>>1;
if (QL <= mid) update(QL,QR,v,o*2);
if (QR > mid) update(QL,QR,v,o*2+1);
push_up(o);
}
}
inline pair<int,int> query(int QL,int QR,int o)
{
int L = tree[o].L , R = tree[o].R;
if (QL <= L && R <= QR) return tree[o].sum;
else
{
push_down(o);
int mid = (L+R)>>1;
SgTreeDataType res = make_pair(-1,0);
if (QL <= mid)
{
pair<int,int> tmp = query(QL,QR,2*o);
if(res.first<=tmp.first)
res=tmp;
}
if (QR > mid)
{
pair<int,int> tmp = query(QL,QR,2*o+1);
if(res.first<=tmp.first)
res=tmp;
}
push_up(o);
return res;
}
}
long long dp[maxn];
int a[maxn];
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n-1;i++)scanf("%d",&a[i]);
a[n]=n;
build_tree(1,n,1);
for(int i=1;i<=n;i++)update(i,i,a[i],1);
long long ans = 0;
for(int i=n-1;i>=1;i--)
{
pair<int,int> tmp = query(i+1,a[i],1);
int m=tmp.second;
dp[i]=dp[m]-(a[i]-m)+n-i;
ans+=dp[i];
}
cout<<ans<<endl;
}