题面

题解

我们先想想，在这个很特殊的图里该怎么走最短路

先设几个量，\(a_i\)表示\([a_i,i-1]\)之间的点都和\(i\)有边（即题中的\(l_i\)），\(l\)表示当前在计算从\(i\)到\([l,i]\)中的所有点的步数总和。那么答案就是\([l,i]-[r+1,i]\)

因为\(a_i\)表示\([a_i,i-1]\)之间的点都和\(i\)有边，那么如果从\(i\)出发，对于所有这个区间中的点，肯定是直接一步跳过去最优。证明显然

记\(mn_i\)表示\(i\)以及它右边所有的点中能跳到的最左边的点，对于所有\([mn_{a_i},a_i-1]\)中的点，肯定能够两步跳到

证明：如果\(mn_{a_i}\)是由\([a_i,i-1]\)中的点跳到的，那么第一步从\(i\)跳到那个点，第二步跳过去。如果是由\(i\)右边的点跳到的，那么从\(i\)第一步跳到右边那个点，再跳过去即可

同理，记\(x=mn_{a_i}\)，所有\([mn_x,x-1]\)之间的点都能\(3\)步跳到，\(y=mn_x\)，则\([mn_y,y-1]\)之间的点都能\(4\)步跳到……

我们把询问变成从\(i\)向左的两个区间相减的形式。那么从\(i\)出发，我们可以把左边的点分为若干段，每一段都有相同的最短步数

然而有可能\(a_i=i-1\)，即每一次都只能往左跳一步，上面的方法就\(gg\)了

让我们看看我们上面是怎么数总步数的……\([a_i,i-1]\)乘个\(1\)，\([mn_{a_i},a_i-1]\)乘个\(2\)，\([mn_x,x-1]\)乘个\(3\)……

我们似乎可以换一个数法，先加上\([1,i-1]\)，再加上\([1,a_i-1]\)，再加上\([1,x-1]\)……

那么这样数出来的答案只要记录一下一共数了\(t\)次，最后减去\(t\times (l-1)\)就是正确答案了！

所以你这转化好像没啥子用啊……跳的次数还是没变啊……

然而我们可以倍增啊！记录一个倍增数组表示跳\(i\)步之后会到哪里，以及跳的这几步里的\(i-1\)的总和

然后就没有然后了

//minamoto#include
    
     #define R register#define ll long long#define fp(i,a,b) for(R int i=a,I=b+1;i
     
      I;--i)#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)template
      
       inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;}using namespace std;char buf[1<<21],*p1=buf,*p2=buf;inline char getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}int read(){    R int res,f=1;R char ch;    while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1);    for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0');    return res*f;}char sr[1<<21],z[20];int K=-1,Z=0;inline void Ot(){fwrite(sr,1,K+1,stdout),K=-1;}void print(R ll x){    if(K>1<<20)Ot();if(x<0)sr[++K]='-',x=-x;    while(z[++Z]=x%10+48,x/=10);    while(sr[++K]=z[Z],--Z);sr[++K]='\n';}const int N=3e5+5,L=21;inline ll gcd(ll x,ll y){return y?gcd(y,x%y):x;}int to[N][L],mn[N],a[N],st[N];ll sum[N][L];int n,top,l,r,x,m;ll p,q,d;ll calc(int x,int y){    ll res=0;int las=0,now,t=0;    if(y>=a[x])return x-y;    las=a[x],res=x-1;    fd(j,19,0)if(to[las][j]>y)t|=(1<