M_sea

洛谷3203 [HNOI2010]弹飞绵羊
LuoguBZOJ分析大力分块。设$step[i]$表示$i$弹出所在块的步数,$to[i]$表示$i$弹出所在块...
扫描右侧二维码阅读全文
18
2018/12

洛谷3203 [HNOI2010]弹飞绵羊

Luogu

BZOJ

分析

大力分块。

设$step[i]$表示$i$弹出所在块的步数,$to[i]$表示$i$弹出所在块后落到哪。

然后一开始就可以$O(n)$预处理出来。

对于查询,每一块跳过去就行,$O(\sqrt{n})$。

对于修改,把所在块全部修改一遍即可,也是$O(\sqrt{n})$。

总时间复杂度是$O(m\sqrt{n})$,还是能氵过去的。

代码

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int MAXN=200000+10;

int n;
int k[MAXN];
int block,belong[MAXN],L[MAXN],R[MAXN];
int step[MAXN],to[MAXN];

inline void build() { //预处理块
    for (re int i=n;i>=1;--i) {
        if (i+k[i]>R[belong[i]]) step[i]=1,to[i]=i+k[i];
        else step[i]=step[i+k[i]]+1,to[i]=to[i+k[i]];
    }
}

inline void change(int x,int y) {
    k[x]=y;
    for (re int i=R[belong[x]];i>=L[belong[x]];--i) {
        if (i+k[i]>R[belong[i]]) step[i]=1,to[i]=i+k[i];
        else step[i]=step[i+k[i]]+1,to[i]=to[i+k[i]];
    }
}

inline int query(int x) {
    int ans=0;
    while (x<=n) ans+=step[x],x=to[x];
    return ans;
}

int main() {
    n=read(),block=sqrt(n);
    for (re int i=1;i<=n;++i) {
        k[i]=read();
        belong[i]=(i-1)/block+1;
        if (belong[i]!=belong[i-1])
            L[belong[i]]=i,R[belong[i-1]]=i-1;
    }
    R[belong[n]]=n; build();
    int m=read();
    while (m--) {
        int op=read();
        if (op==1) printf("%d\n",query(read()+1));
        else if (op==2) { int x=read()+1,y=read(); change(x,y); }
    }
    return 0;
}
最后修改:2019 年 05 月 26 日 03 : 27 PM

4 条评论

  1. ZCDHJ

    orz 分块爷

    1. M_sea
      @ZCDHJ

      不会$LCT$,我还是tcl

  2. smy

    分什么块,lct多好(

    1. M_sea
      @smy

      我不会LCT啊qwq

发表评论