Codeforces Round #353 (Div. 2) E. Trains and Statistic 线段树+dp

题目链接：

http://www.codeforces.com/contest/675/problem/E

题意：

对于第i个站，它与i+1到a[i]的站有路相连，先在求所有站点i到站点j的最短距离之和(1<=i<j<=n)

题解：

这种所有可能都算一遍就会爆的题目，有可能是可以转化为去求每个数对最后答案的贡献，用一些组合计数的方法一般就可以很快算出来。

这里用dp[i]表示第i个站点到后面的所有站的最短距离之和，明显，i+1到a[i]的站，一步就可以到，对于后面的那些点，贪心一下，一定是从max(a[i+1],a[a[i]])的那个点转移过去的，用m表示最大的那个位置，则有：

dp[i]=a[i]-i+dp[m]-(a[i]-m)+n-a[i]；

最后求ans=sum(dp[1]...dp[n])；

#include<iostream>
#include<cstdio>
#include<cstring>
#define lson (o<<1)
#define rson ((o<<1)|1)
#define M (l+((r-l)>>1))
using namespace std;

const int maxn=101010;
typedef __int64 LL;

int n;
int arr[maxn];
LL dp[maxn];
int posv[maxn<<2],maxv[maxn<<2];

int _p,_v;
void update(int o,int l,int r){
    if(l==r){
        maxv[o]=_v;
        posv[o]=l;
    }else{
        if(_p<=M) update(lson,l,M);
        else update(rson,M+1,r);
        if(maxv[lson]>maxv[rson]) posv[o]=posv[lson];
        else posv[o]=posv[rson];
        maxv[o]=max(maxv[lson],maxv[rson]);
    }
}

int ql,qr,_pos;
void query(int o,int l,int r){
    if(ql<=l&&r<=qr){
        if(_v<maxv[o]){
            _pos=posv[o]; _v=maxv[o];
        }
        else if(_v==maxv[o]){
            _pos=max(_pos,posv[o]);
        }
    }else{
        if(ql<=M) query(lson,l,M);
        if(qr>M) query(rson,M+1,r);
    }
}

void init(){
    memset(dp,0,sizeof(dp));
    memset(maxv,0,sizeof(maxv));
}

int main(){
    while(scanf("%d",&n)==1&&n){
        init();
        for(int i=1;i<=n;i++){
            if(i<n) scanf("%d",&arr[i]); 
            else arr[i]=n;
            _p=i,_v=arr[i]; update(1,1,n);
        }
        LL ans=0;
        for(int i=n-1;i>=1;i--){
            _v=-1,ql=i+1,qr=arr[i]; query(1,1,n);
            dp[i]=_pos-i+dp[_pos]+n-arr[i];
            ans+=dp[i];
        } 
        printf("%I64d
",ans);
    } 
    return 0;
}