CF13E Holes

2018-10-08 17:03:54


这题和弹飞绵羊差不多

依然是暴力的分块

在原题基础上多了一问:最后一次落在哪个洞中

先预处理出每个点向后跳到达的点

每次记录 $pre$ ,跳到 $>n$ 的位置或者超出了块的数量就 $break$

但是这样找到的 $pre$ 不一定是最后一个洞

如果它还可以往后跳,就让它继续跳

这个地方坑我 $WA$ 了好几发orz

#include<cstdio>
#include<cstring>
#include<cctype>
#include<cmath>
#include<algorithm>
#define reg register
using namespace std;
const int N=2e5+5;
struct block
{
    int l,r;
}s[500];
int n,m,q,num,a[N],to[N],belong[N],step[N];
inline int read()
{
    int x=0,w=1;
    char c=getchar();
    while (!isdigit(c)&&c!='-') c=getchar();
    if (c=='-') c=getchar(),w=-1;
    while (isdigit(c))
    {
        x=(x<<1)+(x<<3)+c-'0';
        c=getchar();
    }
    return x*w;
}
inline void getblock()
{
    int now=1;
    while (now<=n)
    {
        s[++num].l=now;
        s[num].r=min(n,now+m-1);
        now+=m;
    }
    if (num<m) s[++num].l=num*m+1,s[num].r=n; num=1;
    for (reg int i=1;i<=n;i++)
    {
        if (i>s[num].r) ++num;
        belong[i]=num;
    }
}
inline void change(int l,int r)
{
    for (reg int i=r;i>=l;i--)
    {
        if (i+a[i]>s[belong[i]].r) step[i]=1,to[i]=i+a[i];
        else step[i]=step[i+a[i]]+1,to[i]=to[i+a[i]];
    }
}
int main()
{
    n=read(),q=read(); m=sqrt(n); if (m*m<n) ++m;
    for (reg int i=1;i<=n;a[i++]=read());
    getblock(); change(1,n);
    while (q--)
    {
        int opt=read(),x=read();
        if (opt==1) 
        {
            int ans=step[x],y=to[x],pre=x;
            for (reg int i=belong[x];i<=m&&y<=n;i++) ans+=step[y],pre=y,y=to[y];
            while (pre+a[pre]<=n) pre+=a[pre];
            printf("%d %d\n",pre,ans);
        }
        else
        {
            int y=read(); a[x]=y;
            change(s[belong[x]].l,s[belong[x]].r);
        }
    }
    return 0;
}