LOJ6435 PKUSC2018 星际穿越

这个题吧当时在考场只得了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 ;

}

巴特西

LOJ6435 PKUSC2018 星际穿越

最新文章

热门文章