这是一道有难度的倍增题。
因为\(r_{i}-l_{i}+1\)可以直接计算,故只要求出\(\sum_{j=l_{i}}^{r_{i}} dist(x_{i},j)\),就可以回答询问了。
我们设\(farthest(i,j)\)表示从\(i\)出发,走\(j\)步之内最远能到达哪些点。
接下来我们证明一个结论:\(farthest(i,j)=\min_{k=farthest(i,j-1)}^n l_{k}\),\(farthest(i,0)=l_i\)
首先我们发现,最优的路径一定是从\(x\)出发,向后走最多一格,然后再一直向前走。
显然走了一步,那么只能往前走,\(farthest(i,0)=l_{i}\)。
考虑走了超过一步,那么我们可以在第一步走到一些\(\geq i\)的点\(S\),还有一些点\(j\),\(j\)虽然大于\(i\),但是\(l_{j}>i\),导致\(i,j\)间没有边相连,无法在第一步走到。但是我们仍然可以加入这些点,因为这些点都满足\(l_{j}>i\),而\(l_{i}<i\),故\(farthest(i,p)\)肯定小于\(i\),这些\(j\)并不会对后缀\(min\)造成影响。
这样设\(minl_i=\min_{j=i}^n l_{j}\),那么我们可以从\(i\)连一条边到\(minl_{i}\),表示\(i\)在下一步最远可以到达\(minl_{i}\)。
我们将问题转化成\(solve(i,x)\)表示从\(x\)出发,走到\([i,x)\)的每个点的最短路的和,那么\(ans=solve(l_{i},x)-solve(r_{i}+1,x)\)。
这样,我们可以一步一步找下一个\(minl_{i}\),同时进行计算,是\(O(n^2)\)的。
但是,我们发现这个问题可以用倍增,设\(nxt(i,j)\)表示从\(i\)出发,走\(2^j\)步最远可以到达的点,则\(nxt(i,j)=nxt(nxt(i,j-1),j-1)\)。
然后设\(sum(i,j)=\sum_{k=nxt(i,j)}^{i-1} dist(i,k)\),则不难推出\(sum(i,j)=sum(i,j-1)+sum(nxt(i,j-1),j-1)+2^{j-1}(nxt(i,j-1)-nxt(i,j))\)。
进行\(solve\)函数的过程和预处理倍增的过程基本类似。
要特别注意两点:
- 最后一步要特判,因为\(minl\)有可能直接跳过了我们规定的最小值。
- 第一步也要特判,因为按照我们的推导,\(nxt(i,0)=minl_{i}\),但实际上应该是\(l_{i}\),因为此时我们还无法到大于\(i\)的点上。
#include<bits/stdc++.h>
#define debug(...) std::cerr<<#__VA_ARGS__<<" : "<<__VA_ARGS__<<std::endl
using ll=long long;
const int maxn=300005;
const int maxlog=20;
int n,q,l[maxn],minl[maxn];
int nxt[maxn][maxlog];
ll sum[maxn][maxlog];
ll gcd(ll a,ll b) {
return b==0?a:gcd(b,a%b);
}
ll solve(ll to,ll pos) {
if(to==pos) return 0;
ll ret=0,tot=0;
if(l[pos]>=to) ret+=pos-l[pos],tot=1,pos=l[pos];
for(int j=maxlog-1;~j;j--) {
if(nxt[pos][j]>=to) {
ret+=sum[pos][j]+tot*(pos-nxt[pos][j]);
pos=nxt[pos][j];
tot+=1ll<<(ll)j;
}
}
ret+=(pos-to)*(tot+1);
return ret;
}
int main() {
scanf("%d",&n);
for(int i=2;i<=n;i++)
scanf("%d",&l[i]);
minl[n]=l[n];
for(int i=n-1;i>=2;i--)
minl[i]=std::min(l[i],minl[i+1]);
for(int i=1;i<=n;i++) {
nxt[i][0]=minl[i]; sum[i][0]=i-minl[i];
for(int j=1;j<maxlog;j++) {
nxt[i][j]=nxt[nxt[i][j-1]][j-1];
sum[i][j]=sum[i][j-1]+sum[nxt[i][j-1]][j-1]+(1ll<<ll(j-1))*(nxt[i][j-1]-nxt[i][j]);
}
}
for(int i=1;i<=n;i++) {
for(int j=0;j<maxlog;j++) {
if(!nxt[i][j]) sum[i][j]=0;
}
}
scanf("%d",&q);
while(q--) {
int lef,rig,x;
scanf("%d%d%d",&lef,&rig,&x);
ll a=solve(lef,x)-solve(rig+1,x),b=rig-lef+1,c=gcd(a,b);
printf("%lld/%lld\n",a/c,b/c);
}
return 0;
}