题目：https://loj.ac/problem/6435
题解：https://www.cnblogs.com/HocRiser/p/9166459.html
自己要怎样才能想到怎么做呢……
dp[ t ][ i ] 表示从 [ i , n ] 这些点出发，走 2t 步最左能走到哪。
sm[ t ][ i ] 表示从 [ i , n ] 出发，走到 [ dp[ t ][ i ] , i-1 ] 的最小步数和；比如一个终点 x 贡献的就是 [ i , n ] 里离 x 最近的那个点到 x 的距离。
sm[ t ][ i ] = sm[ t-1 ][ i ] + sm[ t-1 ][ dp[ t-1 ][ i ] ] + ( dp[ t-1 ][ i ] - dp[ t ][ i ] ) * 2t-1
后面那个乘 2t-1 的部分是这样考虑：
新扩展出来的部分是 [ dp[ t ][ i ] , dp[ t-1 ][ i ] ] 这部分。考虑从 [ i , n ] 走到其中一点 x 的长度，一定是 2t-1 再加上一个到 x 具体的步数。
走 2t-1 步之后的步数总和，一定恰好就是 sm[ t-1 ][ dp[ t-1 ][ i ] ] ；
不存在一个在 [ dp[ t ][ i ] , dp[ t-1 ][ i ] ] 里的点 x ，满足 sm[ t-1 ][ dp[ t-1 ][ i ] ] 里包含的步数已经包括了一些 “前 2t-1 步” 的部分。因为如果除去包含在 sm[ t-1 ][ dp[ t-1 ][ i ] ] 里的部分之后，剩余的部分不足 2t-1 步，那么 dp[ t-1 ][ i ] 还可以更多地扩展。
回答询问也可以类似地考虑。把询问 ( [ l , r ] , x ) 拆成 ( [ l , x-1 ] , x ) 和 ( [ r+1 , x-1 ] , x ) ，考虑从 x 开始往左尝试倍增。先走 2t 步走到一个位置 k （k >= l） ，然后可以把 x 移动到 k 那个位置接着尝试倍增；不过这次操作之后的所有路径都要先走 2t 步了，所以此时给答案贡献的是 sm[ t ][ x ] + ( dp[ t ][ x ] - l ) * 2t 。
但是要特别考虑有没有先向右走了一步。
可以先向左走一步，设从 x 走到 x‘，可以认为之后是可以 “从 [ x‘ , n ] 出发 ” 而不是 “ 从 x 点出发 ”了。
因为如果接下来继续向左走，合法。如果接下来从 [ x‘+1 , n ] 的一个点开始走，那么相当于刚才 “向左走” 的一步其实是向右走或者走到了 [ x‘+1 , x ] 的一个点上。
如果是相当于向右走的话，目标点一定是一步可以走到的。因为在最优决策里，下一步是要走到比 x 再往左的一个点，所以目标点一定也能从 x 一步走到。
#include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; int rdn() { int ret=0;bool fx=1;char ch=getchar(); while(ch>‘9‘||ch<‘0‘){if(ch==‘-‘)fx=0;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘)ret=ret*10+ch-‘0‘,ch=getchar(); return fx?ret:-ret; } int Mn(int a,int b){return a<b?a:b;} const int N=3e5+5,K=20; int n,c[N],bin[K],lm,dp[K][N]; ll sm[K][N]; ll gcd(ll a,ll b){return b?gcd(b,a%b):a;} ll cal(int l,int r) { if(l>=c[r])return r-l; ll ret=r-l; r=c[r];//ret=r-l for all based 1 for(int t=18;t>=0;t--) if(dp[t][r]>=l) { ret+=sm[t][r]; r=dp[t][r]; ret+=(ll)(r-l)*bin[t]; } if(r!=l)ret+=r-l; return ret; } int main() { n=rdn(); for(int i=2;i<=n;i++)c[i]=rdn(); bin[0]=1;for(lm=1;bin[lm-1]*2<=n;lm++)bin[lm]=bin[lm-1]*2; lm--; dp[0][n+1]=n+1; for(int i=n;i;i--) { dp[0][i]=Mn(dp[0][i+1],c[i]);//dp[0][1]=0 sm[0][i]=i-dp[0][i]; } for(int t=1;t<=lm;t++) for(int i=1;i<=n;i++) { if(!dp[t-1][i])continue; dp[t][i]=dp[t-1][dp[t-1][i]]; sm[t][i]=sm[t-1][i]+sm[t-1][dp[t-1][i]]+ (ll)(dp[t-1][i]-dp[t][i])*bin[t-1]; } int Q=rdn(),l,r,x; while(Q--) { l=rdn();r=rdn();x=rdn(); ll a=cal(l,x)-cal(r+1,x),b=r-l+1; ll g=gcd(a,b); printf("%lld/%lld\n",a/g,b/g); } return 0; }
LOJ 6435 「PKUSC2018」星际穿越——DP+倍增
原文：https://www.cnblogs.com/Narh/p/10901319.html
