題意：有一張邊權(quán)為 $1$ 的無向圖，對 $i\in [2,n]$，$i$ 與 $[l_i,i?1]$ 間有邊。 $q$ 次詢問 $l,r,x$，表示 $x$ 與 $[l,r]$ 中的所有點(diǎn)的最短路長度的平均值，其中 $l<r<x$。

$n,q\le 3\times 10^5$

考場上以為只能往左走，喜提 0 分。

首先結(jié)論是最多在開始時(shí)往右跳一步。如果跳了多步，因?yàn)槟阕罱K要跳回來，那么一定有一次是跨過了出發(fā)點(diǎn)的，因?yàn)槭请p向邊，所以不如一次跳到這個(gè)點(diǎn)然后往左跳。

先考慮第一步往右的情況，設(shè) $pre(i,j)$ 表示從 $[i,n]$ 中任意一點(diǎn)往左跳最多 $j$ 步能走到的最左邊的點(diǎn)。盡管 $[i+1,n]$ 中有些點(diǎn)可能無法從 $i$ 一步跳到，但就意味著這些點(diǎn)還要再跳一次才能跳到 $i$ 左邊，一定是不優(yōu)的。

由于第一步可以往左，我們再加一個(gè)第一步強(qiáng)制往左的，也就是從 $l_x$ 開始轉(zhuǎn)移。

發(fā)現(xiàn)這個(gè)有結(jié)合性，所以用倍增優(yōu)化即可。

復(fù)雜度 $\mathrm{O}((n+q)\log n)$

#include <iostream> #include <cstdio> #include <cstring> #include <cctype> #define MAXN 300005 using namespace std; typedef long long ll; ll gcd(ll a,ll b){return b? gcd(b,a%b):a;} inline int read() {int ans=0;char c=getchar();while (!isdigit(c)) c=getchar();while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();return ans; } int a[MAXN],pre[MAXN][20]; ll sum[MAXN][20]; ll query(int p,int x) {if (a[x]<=p) return x-p;int pos=a[x],cur=1;ll ans=x-a[x];for (int i=19;i>=0;i--)if (pre[pos][i]>=p){ans+=sum[pos][i]+(ll)(pos-pre[pos][i])*cur;pos=pre[pos][i];cur+=(1<<i);}return ans+(ll)(pos-p)*(cur+1); } int main() {int n=read();pre[n+1][0]=2e9;for (int i=2;i<=n;i++) a[i]=read();for (int i=n;i>=1;i--) sum[i][0]=i-(pre[i][0]=min(pre[i+1][0],a[i]));for (int j=1;j<20;j++)for (int i=1;i<=n;i++){pre[i][j]=pre[pre[i][j-1]][j-1];sum[i][j]=sum[i][j-1]+sum[pre[i][j-1]][j-1]+(1ll<<(j-1))*(pre[i][j-1]-pre[i][j]);}for (int q=read();q;q--){int l,r,x;l=read(),r=read(),x=read();ll ans=query(l,x)-query(r+1,x),y=r-l+1;ll d=gcd(ans,y);ans/=d,y/=d;printf("%lld/%lld\n",ans,y);}return 0; }

總結(jié)

以上是生活随笔為你收集整理的【PKUSC2018】星际穿越【结论】【倍增dp】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。