这个题吧当时在考场只得了45分 然后70分的性质都分析到了 不知道为啥就是写萎蛋了
哎 当时还是too young too simple
看了一下julao们的博客这个题有两种做法
一个是比较费脑子的倍增做法
一个是比较费体力【大雾 的主席树做法
打死也不写数据结构的我当然还是学第一个啦
首先我们可以分析到要么往右跳一步再往左跳 要么一直往左跳
这个过程我们可以O(n^2)做 通过更新mn[x]就是每个点往左跳最远的位置 这样就可以一步一步往左跳
然后这个过程可以优化一下就是从右往左扫一遍更新先往右跳的 比较好写233
然后我们可以发现这个mn它是一段一段的 所以我们一步一步跳很浪费时间
可以联想到倍增 也就是把一步一步换成2^i步这样 这样可以lgn换掉一个n
所以我们可以用f[x][i]表示x走2^i步最远的位置
我们再来观察题目性质
它每次询问的是x走到一段区间的距离和 这个问题显然是可以差分的
也就是x->[l,r] = x->[l,x] – x->[r+1,x]
我们还可以观察到这个跳跃正反是一样的 于是我们要做的就是求calc(l,x) – calc(r+1,x)
那么我们可以预处理一个s[x][i]数组表示x~f[x][i]这些点跳到f[x][i]的最少步数和
所以我们calc要做的就是[l,x]这些点跳到x的步数和 也可以反过来做就是x象征性的往左跳 然后实际上统计的都是这些点到x的距离【有点拗口 但好像就是这么理解的
然后跳的话。。。就是统计每次2^j跳的和然后加进来就行了
有些小trick放在代码里了 不影响正常理解应该 只是大大缩短了代码量
//Love and Freedom.
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#define ll long long
#define inf 20021225
#define N 300010
#define LG 20
using namespace std;int s[N][LG],f[N][LG];
int w[N],n,l,r,x,Q;
int gcd(int x,int y){return y?gcd(y,x%y):x;}
ll calc(int l,int r)
{
if(w[r]<=l) return r-l;
ll ans=r-w[r]; r=w[r]; int tot=;
for(int i=LG-;~i;i--) if(f[r][i]>l)
ans+=s[r][i]+tot*(r-f[r][i]),r=f[r][i],tot+=<<i;
return ans+(r-l)*(tot+);
}
int main()
{
scanf("%d",&n); w[]=;
for(int i=;i<=n;i++) scanf("%d",&w[i]);
f[n][]=w[n]; s[n][]=n-w[n];
for(int i=n-;i;i--) f[i][]=min(f[i+][],w[i]),s[i][]=i-f[i][];
for(int i=;i<LG;i++) for(int j=;j<=n;j++) if(f[j][i-])
f[j][i]=f[f[j][i-]][i-],
s[j][i]=s[j][i-]+s[f[j][i-]][i-]+(f[j][i-]-f[j][i])*(1ll<<(i-));
scanf("%d",&Q);
while(Q--)
{
scanf("%d%d%d",&l,&r,&x);
ll tp=calc(l,x)-calc(r+,x),dn=r-l+;
ll g=gcd(tp%dn,dn);
printf("%lld/%lld\n",tp/g,dn/g);
}
return ;
}
