C,Dより簡単に解けた…。
http://codeforces.com/contest/675/problem/E
問題
N頂点からなる有向グラフを考える。
頂点iからは、(i+1)~A[i]の範囲の頂点に1手で移動できる。
頂点対(i,j)(i<j)に対して、R(i,j)をi→jに至る対象の辺の遷移回数とする。
R(i,j)の総和を求めよ。
解法
S(i) := R(i,j)の総和
とする。
iの大きい順にS(i)を求めていこう。
iから(i+1)~A[i]には1手で移動できる。よってR(i,i+1)~R(i,A[i])はいずれも1である。
1手で移動できないA[i]以降の範囲に移動したいときは、(i+1)~A[i]の間の頂点xのうち、A[x]が最大のところに遷移しよう。
これはx=(i+1)~Nとなるxに対し、(x,A[x])が昇順になるようにならべた配列やsetを管理し、二分探索を用いることで高速に求められる。
そのようなxが定まるとする。
S(i)は以下で求められる。
- (i+1)~iは1手で移動するのでA[i]-iをS(i)に足しこむ。
- (A[i]+1)以降の頂点への遷移は、初回xへ移動してその後はxから移動する場合と同じなのでS(x) + (N-A[i])
- ただし、S(x)はxから(x+1)~A[i]に移動する分も足しこまれている。これらはそもそもiから1手で移動できるので、その文(A[i]-x)を引く。
int N; int A[101010]; ll S[101010]; ll ret; void solve() { int i,j,k,l,r,x,y; string s; cin>>N; FOR(i,N-1) cin>>A[i],A[i]--; A[N-1]=N; set<pair<int,int>> L; L.insert({N-1,N}); for(i=N-2;i>=0;i--) { while(L.begin()->second<=A[i]) L.erase(L.begin()); auto it=L.lower_bound({A[i]+1,0}); it--; x=it->first; S[i]=A[i]-i+S[x]-(A[i]-x)+N-1-A[i]; L.insert({i,A[i]}); ret += S[i]; } cout<<ret<<endl; }
まとめ
DもEもコード短いし、結局Cに一番苦戦した。