这个题吧当时在考场只得了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
      
       #include
       
        #include
        
         #include
         
          #define ll long long#define inf 20021225#define N 300010#define LG 20using 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=1;    for(int i=LG-1;~i;i--)    if(f[r][i]>l)        ans+=s[r][i]+tot*(r-f[r][i]),r=f[r][i],tot+=1<