题目大概说有n（<=10W）个车站，每个车站i卖到车站i+1...a[i]的票，p[i][j]表示从车站i到车站j所需买的最少车票数，求所有的p[i][j]（i<j）的和。
好难，不会写。。
- dp[i]表示Σp[i][j]（j>i）
- 转移是dp[i]=dp[k]+(n-i)-(a[i]-k)，其中k是i能直接买到的站中能直接买到最远的站，即a[k]=max(a[i+1]...a[a[i]])，这个可以用线段树快速查询
为什么从k转移？因为i+1...a[i]中除了k外能直接买到的车站都是k的子集，贪心地选择能延伸最远的k一定是没错的。
为什么转移方程是这样？dp[i]，就是表示从i出发到达各个j（j>i）城市所需最少票数和，而这(n-i)个车站，对于在a[i]范围内只要从车站i买一张车票就直达了，对于大于a[i]的需要买一张车票到车站k再转车，所以就是dp[k]+(n-i)；不过在dp[k]里面重复算了，要去k+1...a[i]范围的车站，明明可以直达却先到达k再转车，这多买了一张车票，所以减去(a[i]-k)。
#include<cstdio>
#include<cstring>
using namespace std;
#define MAXN 111111 struct Node{
int mmm,idx;
Node():mmm(){}
}tree[MAXN<<];
int x,y,N;
void update(int i,int j,int k){
if(i==j){
tree[k].mmm=y;
tree[k].idx=i;
return;
}
int mid=i+j>>;
if(x<=mid) update(i,mid,k<<);
else update(mid+,j,k<<|);
if(tree[k<<].mmm>tree[k<<|].mmm){
tree[k]=tree[k<<];
}else{
tree[k]=tree[k<<|];
}
}
Node query(int i,int j,int k){
if(x<=i && j<=y){
return tree[k];
}
int mid=i+j>>;
Node ret;
if(x<=mid){
Node tmp=query(i,mid,k<<);
if(ret.mmm<tmp.mmm) ret=tmp;
}
if(y>mid){
Node tmp=query(mid+,j,k<<|);
if(ret.mmm<tmp.mmm) ret=tmp;
}
return ret;
} int a[MAXN];
long long d[MAXN];
int main(){
int n;
scanf("%d",&n);
for(N=; N<n; N<<=);
for(int i=; i<n; ++i){
scanf("%d",a+i);
x=i; y=a[i];
update(,N,);
}
x=n; y=n;
update(,N,);
for(int i=n-; i>=; --i){
x=i+; y=a[i];
Node tmp=query(,N,);
d[i]=d[tmp.idx]+n-i-(a[i]-tmp.idx);
}
long long res=;
for(int i=; i<=n; ++i){
res+=d[i];
}
printf("%lld",res);
return ;
}